home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / superopt.zip / SUPEROPT.C < prev    next >
C/C++ Source or Header  |  1992-11-28  |  81KB  |  2,714 lines
  1. /* Superoptimizer.  Finds the shortest instruction sequences for an
  2.    arbitrary function f(x,y) where x and y are integers.  The algorithm is
  3.    based on exhaustive search with backtracking and iterative deepening.
  4.  
  5.    Copyright (C) 1991, 1992 Free Software Foundation, Inc.
  6.  
  7.    This program is free software; you can redistribute it and/or modify it
  8.    under the terms of the GNU General Public License as published by the
  9.    Free Software Foundation; either version 2, or (at your option) any
  10.    later version.
  11.  
  12.    This program is distributed in the hope that it will be useful, but
  13.    WITHOUT ANY WARRANTY; without even the implied warranty of
  14.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15.    General Public License for more details.
  16.  
  17.    You should have received a copy of the GNU General Public License along
  18.    with this program; see the file COPYING.  If not, write to the Free
  19.    Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. #include <stdio.h>
  22.  
  23. #define ARITH_BITS BITS_PER_WORD
  24. #include "superopt.h"
  25. #include "run_program.def"
  26. #include "version.h"
  27.  
  28. int goal_function_arity;
  29. enum goal_func goal_function;
  30. word (*eval_goal_function) (const word *);
  31.  
  32. int flag_output_assembler = 0;
  33. int flag_use_carry = 1;
  34.  
  35. /* Counts the number of solutions found.  Flags to top loop that it should
  36.    not go deeper.  */
  37. int success;
  38.  
  39. #ifdef TIMING
  40. #include <sys/types.h>
  41. #include <sys/time.h>
  42. #include <sys/resource.h>
  43.  
  44. int
  45. cputime ()
  46. {
  47.     struct rusage rus;
  48.  
  49.     (void) getrusage (0, &rus);
  50.     return (rus.ru_utime.tv_sec + rus.ru_stime.tv_sec) * 1000
  51.       + (rus.ru_utime.tv_usec + rus.ru_stime.tv_usec) / 1000;
  52. }
  53.  
  54. int time[100];
  55. #endif
  56.  
  57. #ifdef STATISTICS
  58. unsigned int heuristic_reject_count = 0;
  59. unsigned int heuristic_accept_count = 0;
  60. #endif
  61.  
  62. char *insn_name[] =
  63. {
  64. #undef    DEF_INSN
  65. #define DEF_INSN(SYM,CLASS,NAME) NAME,
  66. #include "insn.def"
  67. };
  68.  
  69. char insn_class[] =
  70. {
  71. #undef    DEF_INSN
  72. #define DEF_INSN(SYM,CLASS,NAME) CLASS,
  73. #include "insn.def"
  74. };
  75.  
  76. /* Initialize the "immediate" values in the top registers.  */
  77. void
  78. init_immediates(word *values)
  79. {
  80.   int i;
  81.   for (i = -1; i < BITS_PER_WORD; i++)
  82.     values[0x20 + i] = i;
  83.  
  84.   values[0x20 - 2] = VALUE_MIN_SIGNED;
  85.   values[0x20 - 3] = VALUE_MAX_SIGNED;
  86. }
  87.  
  88. inline word
  89. random_word(void)
  90. {
  91. #ifdef __hpux
  92.   return mrand48();
  93. #else
  94.   /* random returns 31 bits.  We need 32.  */
  95.   return random() ^ (random() << 1);
  96. #endif
  97. }
  98.  
  99. char *
  100. xrealloc (ptr, size)
  101.      char *ptr;
  102.      unsigned size;
  103. {
  104.   char *result = (char *) realloc (ptr, size);
  105.   if (!result)
  106.     abort ();
  107.   return result;
  108. }
  109.  
  110. char *
  111. xmalloc (size)
  112.      unsigned size;
  113. {
  114.   register char *val = (char *) malloc (size);
  115.  
  116.   if (val == 0)
  117.     abort ();
  118.   return val;
  119. }
  120.  
  121. #define RECURSE(opcode, s1, s2, prune_hint) \
  122.   recurse(opcode, n_values, s1, s2, v, 1, sequence, n_insns, values,    \
  123.       n_values + 1, goal_value, allowed_cost, co, prune_hint)
  124. #define CRECURSE_2OP(opcode, d, s1, s2, cost, prune_hint) \
  125.   recurse(opcode, d, s1, s2, v, cost, sequence, n_insns, values,    \
  126.       n_values, goal_value, allowed_cost, co, prune_hint)
  127. #define CRECURSE_NEW(opcode, d, s1, s2, cost, prune_hint) \
  128.   recurse(opcode, d, s1, s2, v, cost, sequence, n_insns, values,    \
  129.       n_values + 1, goal_value, allowed_cost, co, prune_hint)
  130.  
  131. /* Save the last generated instruction and recursively call `synth', if we
  132.    are not at a leaf node.  Otherwise test the computed value and
  133.    back-track.  This function is extremely critical for the performance!
  134.  
  135.    OPCODE is the opcode of the insn that was just generated.
  136.  
  137.    D is the destination register.
  138.  
  139.    S1 is the left source register or immediate reference.  It is an
  140.    immediate reference if IMMEDIATE_P(S1) is true.
  141.  
  142.    S2 is the right source register or immediate reference.  It is an
  143.    immediate reference if IMMEDIATE_P(S2) is true.
  144.  
  145.    V is the computed result from "rD = rS1 OPCODE rS2".
  146.  
  147.    COST is the cost of OPCODE with the the actual operands.
  148.  
  149.    SEQUENCE is the insn sequence so far, excluding the just generated insn.
  150.  
  151.    N_INSNS is the number of insns in SEQUENCE.
  152.  
  153.    VALUES contains the values in register 0..N_VALUES.
  154.  
  155.    N_VALUES is the number of registers that have been assigned values by
  156.    the insns so far.
  157.  
  158.    GOAL_VALUE is the value we aim at, when the sequence is ready.
  159.  
  160.    ALLOWED_COST is the maximum allowed cost of the remaining sequence.
  161.  
  162.    CY is the carry flag.  It is negative if no instruction has yet defined
  163.    it (this to pruning the search tree), and otherwise takes the values 0
  164.    or 1 according to the conventions of the current target.
  165.  
  166.    PRUNE_HINT contains flags to assist pruning of the search tree.  */
  167.  
  168. static inline void
  169. recurse(opcode_t opcode,
  170.     int d,
  171.     int s1,
  172.     int s2,
  173.     word v,
  174.     int cost,
  175.     insn_t *sequence,
  176.     int n_insns,
  177.     word *values,
  178.     int n_values,
  179.     const word goal_value,
  180.     int allowed_cost,
  181.     int cy,
  182.     int prune_flags)
  183. {
  184.   insn_t insn;
  185.  
  186.   /* Update the remaining allowed cost with the cost of the last
  187.      instruction.  */
  188.   allowed_cost -= cost;
  189.  
  190.   if (allowed_cost > 0)
  191.     {
  192.       /* ALLOWED_COST is still positive, meaning we can generate more
  193.      instructions.  */
  194.       word old_d;
  195.  
  196.       old_d = values[d];    /* Remember old value of dest. reg.  */
  197.       values[d] = v;
  198.  
  199.       insn.opcode = opcode;
  200.       insn.s1 = s1;
  201.       insn.s2 = s2;
  202.       insn.d = d;
  203.       sequence[n_insns] = insn;
  204.  
  205.       synth(sequence, n_insns + 1, values, n_values,
  206.         goal_value, allowed_cost, cy, prune_flags);
  207.  
  208.       values[d] = old_d;    /* Restore value of dest. reg. */
  209.     }
  210.   else if (goal_value == v)
  211.     {
  212.       /* We are at a leaf node and got the right answer for the
  213.      random value operands.  However, we probably have an
  214.      incorrect sequence.  Call test_sequence to find out.  */
  215.  
  216.       insn.opcode = opcode;
  217.       insn.s1 = s1;
  218.       insn.s2 = s2;
  219.       insn.d = d;
  220.       sequence[n_insns] = insn;
  221.       test_sequence(sequence, n_insns + 1);
  222.  
  223. #ifdef STATISTICS
  224.   heuristic_accept_count++;
  225. #endif
  226.  
  227.     }
  228. #ifdef STATISTICS
  229.   else
  230.     heuristic_reject_count++;
  231. #endif
  232. }
  233.  
  234. #define NAME(op) operand_names[op]
  235. static char *operand_names[256]=
  236. {
  237. #if SPARC
  238.   "%i0", "%i1", "%i2", "%i3", "%i4", "%i5", "%i6", "%i7",
  239. #elif RS6000
  240.   "r3", "r4", "r5", "r6", "r7", "r8", "r9", "r10",
  241. #elif M88000
  242.   "r2", "r3", "r4", "r5", "r6", "r7", "r8", "r9",
  243. #elif AM29K
  244.   "lr2", "lr3", "lr4", "lr5", "lr6", "lr7", "lr8", "lr9",
  245. #elif M68000
  246.   "d0", "d1", "d2", "d3", "d4", "d5", "d6", "d7",
  247. #elif I386
  248.   "%eax", "%edx", "%ecx", "%ebx", "%esi", "%edi", "%noooo!", "%crash!!!",
  249. #elif PYR
  250.   "pr0", "pr1", "pr2", "pr3", "pr4", "pr5", "pr6", "pr7",
  251. #else
  252. #error no register names for this CPU
  253. #endif
  254.   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  255. #if SPARC
  256.   "???%hi(0x7fffffff)","%hi(0x80000000)","-1","%g0","1","2","3","4","5","6",
  257.   "7","8","9","10","11","12","13","14","15","16","17","18","19",
  258.   "20","21","22","23","24","25","26","27","28","29","30","31",
  259. #elif RS6000
  260.   "0x7fff","0x8000","-1","0","1","2","3","4","5","6",
  261.   "7","8","9","10","11","12","13","14","15","16","17","18","19",
  262.   "20","21","22","23","24","25","26","27","28","29","30","31",
  263. #elif M88000
  264.   "hi16(0x7fffffff)","hi16(0x80000000)","-1","r0","1","2","3","4","5","6",
  265.   "7","8","9","10","11","12","13","14","15","16","17","18","19",
  266.   "20","21","22","23","24","25","26","27","28","29","30","31",
  267. #elif AM29K
  268.   "0x7fff","0x8000","-1","0","1","2","3","4","5","6",
  269.   "7","8","9","10","11","12","13","14","15","16","17","18","19",
  270.   "20","21","22","23","24","25","26","27","28","29","30","31",
  271. #elif M68000
  272.   "#0x7fffffff","#0x80000000","#-1","#0","#1","#2","#3","#4","#5","#6",
  273.   "#7","#8","#9","#10","#11","#12","#13","#14","#15","#16","#17","#18","#19",
  274.   "#20","#21","#22","#23","#24","#25","#26","#27","#28","#29","#30","#31",
  275. #elif I386
  276.   "$0x7fffffff","$0x80000000","$-1","$0","$1","$2","$3","$4","$5","$6",
  277.   "$7","$8","$9","$10","$11","$12","$13","$14","$15","$16","$17","$18","$19",
  278.   "$20","$21","$22","$23","$24","$25","$26","$27","$28","$29","$30","$31",
  279. #elif PYR
  280.   "$0x7fffffff","$0x80000000","$-1","$0","$1","$2","$3","$4","$5","$6",
  281.   "$7","$8","$9","$10","$11","$12","$13","$14","$15","$16","$17","$18","$19",
  282.   "$20","$21","$22","$23","$24","$25","$26","$27","$28","$29","$30","$31",
  283. #else
  284. #error no constant syntax for this CPU
  285. #endif
  286.   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  287.   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  288.   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  289.   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  290.   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  291.   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
  292. };
  293.  
  294. /* Output INSN in assembler mnemonic format on stdout.  */
  295.  
  296. void
  297. output_assembler(insn_t insn)
  298. {
  299.   int d, s1, s2;
  300.  
  301.   d = insn.d;
  302.   s1 = insn.s1;
  303.   s2 = insn.s2;
  304.  
  305.   printf("\t");
  306.   switch (insn.opcode)
  307.     {
  308. #if SPARC
  309.     case COPY:
  310.       if (IMMEDIATE_P(s1) && (IMMEDIATE_VAL(s1) & 0x1fff) == 0)
  311.     printf("sethi    %s,%s",NAME(s1),NAME(d));
  312.       else
  313.     printf("mov    %s,%s",NAME(s1),NAME(d));
  314.       break;
  315.     case ADD:    printf("add    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  316.     case ADD_CI:printf("addx    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  317.     case ADD_CO:printf("addcc    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  318.     case ADD_CIO:printf("addxcc    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  319.     case SUB:
  320.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  321.     printf("xnor    %%g0,%s,%s",NAME(s2),NAME(d));
  322.       else
  323.     printf("sub    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));
  324.       break;
  325.     case SUB_CI:printf("subx    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  326.     case SUB_CO:printf("subcc    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  327.     case SUB_CIO:printf("subxcc    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  328.     case AND:    printf("and    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  329.     case IOR:    printf("or    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  330.     case XOR:    printf("xor    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  331.     case ANDC:    printf("andn    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  332.     case IORC:    printf("orn    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  333.     case EQV:    printf("xnor    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  334.     case LSHIFTR:printf("srl    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  335.     case ASHIFTR:printf("sra    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  336.     case SHIFTL:printf("sll    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  337. #elif RS6000
  338.     case COPY:
  339.       if (IMMEDIATE_P(s1))
  340.     {
  341.       if (IMMEDIATE_VAL(s1) >= 0 && IMMEDIATE_VAL(s1) < 0x8000)
  342.         printf("lil    %s,0x%x",NAME(d),IMMEDIATE_VAL(s1));
  343.       else
  344.         printf("liu    %s,%s",NAME(d),NAME(s1));
  345.     }
  346.       else
  347.     printf("oril    %s,%s,0",NAME(d),NAME(s1));
  348.       break;
  349.     case ADD:
  350.       if (IMMEDIATE_P(s2))
  351.     {
  352.       if (IMMEDIATE_VAL(s2) + 0x4000 < 0x8000)
  353.         printf("cal    %s,%d(%s)",NAME(d),IMMEDIATE_VAL(s2),NAME(s1));
  354.       else if ((IMMEDIATE_VAL(s2) & 0xffff) == 0)
  355.         printf("cau    %s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2) >> 16);
  356.       else
  357.         abort ();
  358.     }
  359.       else
  360.     printf("cax     %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  361.       break;
  362.     case ADD_CO:
  363.       if (IMMEDIATE_P(s2))
  364.     printf("ai    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  365.       else
  366.     printf("a    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  367.       break;
  368.     case ADD_CIO:
  369.       if (IMMEDIATE_P(s2))
  370.     {
  371.       if (IMMEDIATE_VAL(s2) == -1)
  372.         printf("ame    %s,%s",NAME(d),NAME(s1));
  373.       else if (IMMEDIATE_VAL(s2) == 0)
  374.         printf("aze    %s,%s",NAME(d),NAME(s1));
  375.     }
  376.       else
  377.     printf("ae    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  378.       break;
  379.     case SUB:
  380.       if (IMMEDIATE_P(s1))
  381.     {
  382.       if (IMMEDIATE_VAL(s1) == 0)
  383.         printf("neg    %s,%s",NAME(d),NAME(s2));
  384.       else if (IMMEDIATE_VAL(s1) == -1)
  385.         printf("nand    %s,%s,%s",NAME(d),NAME(s2),NAME(s2));
  386.     }
  387.       else abort();
  388.       break;
  389.     case ADC_CO:
  390.       if (IMMEDIATE_P(s1))
  391.     printf("sfi    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  392.       else
  393.     printf("sf    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  394.       break;
  395.     case ADC_CIO:
  396.       if (IMMEDIATE_P(s1))
  397.     {
  398.       if (IMMEDIATE_VAL(s1) == -1)
  399.         printf("sfme    %s,%s",NAME(d),NAME(s2));
  400.       else if (IMMEDIATE_VAL(s1) == 0)
  401.         printf("sfze    %s,%s",NAME(d),NAME(s2));
  402.       else abort();
  403.     }
  404.       else
  405.     printf("sfe    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  406.       break;
  407.     case AND:
  408.       if (IMMEDIATE_P(s2))
  409.     {
  410.       if (IMMEDIATE_VAL(s2) == 0x80000000)
  411.         printf("rlinm    %s,%s,0,0,0",NAME(d),NAME(s1));
  412.       else if (IMMEDIATE_VAL(s2) == 0x7fffffff)
  413.         printf("rlinm    %s,%s,0,1,31",NAME(d),NAME(s1));
  414.       else if (IMMEDIATE_VAL(s2) == 1)
  415.         printf("rlinm    %s,%s,0,31,31",NAME(d),NAME(s1));
  416.       else abort();
  417.     }
  418.       else
  419.     printf("and    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  420.       break;
  421.     case IOR:
  422.       if (IMMEDIATE_P(s2))
  423.     {
  424.       if (IMMEDIATE_VAL(s2) == 0x80000000)
  425.         printf("oriu    %s,%s,0x8000",NAME(d),NAME(s1));
  426.       else abort();
  427.     }
  428.       else
  429.     printf("or    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  430.       break;
  431.     case XOR:
  432.       if (IMMEDIATE_P(s2))
  433.     {
  434.       if (IMMEDIATE_VAL(s2) == 1)
  435.         printf("xoril\t%s,%s,1",NAME(d),NAME(s1));
  436.       else if (IMMEDIATE_VAL(s2) == 0x80000000)
  437.         printf("xoriu\t%s,%s,0x8000",NAME(d),NAME(s1));
  438.       else abort();
  439.     }
  440.       else
  441.     printf("xor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  442.       break;
  443.     case ANDC:    printf("andc    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  444.     case IORC:    printf("orc    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  445.     case EQV:    printf("eqv    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  446.     case NAND:    printf("nand    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  447.     case NOR:    printf("nor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  448.     case LSHIFTR:
  449.       if (IMMEDIATE_P(s2))
  450.     printf("sri    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  451.       else
  452.     printf("sre    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  453.       break;
  454.     case ASHIFTR_CON:
  455.       if (IMMEDIATE_P(s2))
  456.     printf("srai    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  457.       else
  458.     printf("srea    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  459.       break;
  460.     case SHIFTL:
  461.       if (IMMEDIATE_P(s2))
  462.     printf("sli    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  463.       else
  464.     printf("sle    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  465.       break;
  466.     case ROTATEL:
  467.       if (IMMEDIATE_P(s2))
  468.     printf("rlinm    %s,%s,%s,0,31",NAME(d),NAME(s1),NAME(s2));
  469.       else
  470.     printf("rlnm    %s,%s,%s,0,31",NAME(d),NAME(s1),NAME(s2));
  471.       break;
  472.     case ABSVAL:printf("abs    %s,%s",NAME(d),NAME(s1));break;
  473.     case NABSVAL:printf("nabs    %s,%s",NAME(d),NAME(s1));break;
  474.     case DOZ:
  475.       if (IMMEDIATE_P(s1))
  476.     printf("dozi    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  477.       else
  478.     printf("doz    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  479.       break;
  480.     case MUL:
  481.       if (IMMEDIATE_P(s1))
  482.     printf("muli    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  483.       else
  484.     printf("muls    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  485.       break;
  486.       
  487. #elif M88000
  488.     case COPY:
  489.       if (IMMEDIATE_P(s1))
  490.     {
  491.       if ((IMMEDIATE_VAL(s1) & 0xffff) == 0)
  492.         printf("or.u    %s,r0,0x%x",NAME(d),IMMEDIATE_VAL(s1));
  493.       else if ((IMMEDIATE_VAL(s1) & 0xffff0000) == 0)
  494.         printf("or    %s,r0,0x%x",NAME(d),IMMEDIATE_VAL(s1));
  495.       else if ((IMMEDIATE_VAL(s1) & 0xffff0000) == 0xffff0000)
  496.         printf("subu    %s,r0,0x%x",NAME(d),-IMMEDIATE_VAL(s1));
  497.       else
  498.         {
  499.           word x = IMMEDIATE_VAL(s1);
  500.           int i, j;
  501.           for (i = 31; i > 0; i--)
  502.         if ((x & (1 << i)) != 0)
  503.           break;
  504.           for (j = i; j >= 0; j--)
  505.         if ((x & (1 << j)) == 0)
  506.           break;
  507.           printf("set    %s,r0,%d<%d>",NAME(d), i - j, j + 1);
  508.         }
  509.     }
  510.       else
  511.     printf("or    %s,%s",NAME(d),NAME(s1));
  512.       break;
  513.     case ADD:    printf("addu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  514.     case ADD_CI:printf("addu.ci    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  515.     case ADD_CO:printf("addu.co    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  516.     case ADD_CIO:
  517.       if (IMMEDIATE_P(s2))
  518.     {
  519.       if (IMMEDIATE_VAL(s2) == -1)
  520.         {
  521.           printf("subu.cio %s,%s,r0",NAME(d),NAME(s1));
  522.           break;
  523.         }
  524.       if (IMMEDIATE_VAL(s2) != 0)
  525.         abort();
  526.     }
  527.       printf("addu.cio %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  528.       break;      
  529.     case SUB:
  530.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  531.     printf("xor.c    %s,%s,r0",NAME(d),NAME(s2));
  532.       else
  533.     printf("subu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  534.       break;
  535.     case ADC_CI:printf("subu.co    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  536.     case ADC_CO:printf("subu.co    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  537.     case ADC_CIO:printf("subu.cio %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  538.     case AND:
  539.       if (IMMEDIATE_P(s2))
  540.     {
  541.       if (IMMEDIATE_VAL(s2) == 0x80000000)
  542.         printf("mask.u    %s,%s,0x8000",NAME(d),NAME(s1));
  543.       else if (IMMEDIATE_VAL(s2) == 0x7fffffff)
  544.         printf("and.u    %s,%s,0x7fff",NAME(d),NAME(s1));
  545.       else if (IMMEDIATE_VAL(s2) == 1)
  546.         printf("mask    %s,%s,1",NAME(d),NAME(s1));
  547.       else abort();
  548.     }
  549.       else
  550.     printf("and    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  551.       break;
  552.     case IOR:
  553.       if (IMMEDIATE_P(s2))
  554.     {
  555.       if ((IMMEDIATE_VAL(s2) & 0xffff) == 0)
  556.         printf("or.u    %s,%s,0x%x",NAME(d),NAME(s1),
  557.            IMMEDIATE_VAL(s2)>>16);
  558.       else if (IMMEDIATE_VAL(s2) < 0x10000)
  559.         printf("or    %s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  560.       else abort();
  561.     }
  562.       else
  563.     printf("or    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  564.       break;
  565.     case XOR:
  566.       if (IMMEDIATE_P(s2))
  567.     {
  568.       if ((IMMEDIATE_VAL(s2) & 0xffff) == 0)
  569.         printf("xor.u    %s,%s,0x%x",NAME(d),NAME(s1),
  570.            IMMEDIATE_VAL(s2)>>16);
  571.       else if (IMMEDIATE_VAL(s2) < 0x10000)
  572.         printf("xor    %s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  573.       else abort();
  574.     }
  575.       else
  576.     printf("xor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  577.       break;
  578.     case ANDC:    printf("and.c    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  579.     case IORC:    printf("or.c    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  580.     case EQV:    printf("xor.c    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  581.     case LSHIFTR:printf("extu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  582.     case ASHIFTR:printf("ext    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  583.     case SHIFTL:printf("mak    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  584.     case ROTATEL:
  585.       printf("rot    %s,%s,%d",NAME(d),NAME(s1),32-IMMEDIATE_VAL(s2));
  586.       break;
  587.     case FF1:
  588.       printf("ff1    %s,%s",NAME(d),NAME(s1)); break;
  589.     case FF0:
  590.       printf("ff0    %s,%s",NAME(d),NAME(s1)); break;
  591.     case CMPPAR:
  592.       if (IMMEDIATE_P(s2))
  593.     printf("cmp    %s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  594.       else if (IMMEDIATE_P(s1))
  595.     printf("cmp    %s,r0,%s",NAME(d),NAME(s2));
  596.       else
  597.     printf("cmp    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  598.       break;
  599.     case EXTS1:
  600.       printf("ext    %s,%s,1<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  601.       break;      
  602.     case EXTS2:
  603.       printf("ext    %s,%s,2<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  604.       break;      
  605.     case EXTU1:
  606.       printf("extu    %s,%s,1<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  607.       break;      
  608.     case EXTU2:
  609.       printf("extu    %s,%s,2<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  610.       break;      
  611.     case MUL:
  612.       printf("mul    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  613.       break;      
  614. #elif AM29K
  615.     case COPY:
  616.       if (IMMEDIATE_P(s1))
  617.     {
  618.       if (IMMEDIATE_VAL(s1) < 0x10000)
  619.         printf("const    %s,0x%x",NAME(d),IMMEDIATE_VAL(s1));
  620.       else if (-IMMEDIATE_VAL(s1) < 0x10000)
  621.         printf("constn    %s,-0x%x",NAME(d),-IMMEDIATE_VAL(s1));
  622.       else if (IMMEDIATE_VAL(s1) == 0x80000000)
  623.         printf("cpeq    %s,gr1,gr1",NAME(d));
  624.       else abort();
  625.     }
  626.       else
  627.     printf("or    %s,%s,0",NAME(d),NAME(s1));
  628.       break;
  629.     case ADD_CO:
  630.       if (IMMEDIATE_P(s2) && (signed_word) IMMEDIATE_VAL(s2) < 0)
  631.     printf("sub    %s,%s,0x%x",NAME(d),NAME(s1),-IMMEDIATE_VAL(s2));
  632.       else
  633.     printf("add    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  634.       break;
  635.     case ADD_CIO:
  636.       if (IMMEDIATE_P(s2) && (signed_word) IMMEDIATE_VAL(s2) < 0)
  637.     printf("subc    %s,%s,0x%x",NAME(d),NAME(s1),-IMMEDIATE_VAL(s2));
  638.       else
  639.     printf("addc    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  640.       break;
  641.     case SUB:
  642.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  643.     printf("nor    %s,%s,0",NAME(d),NAME(s2));
  644.       else abort();
  645.       break;
  646.     case ADC_CO:printf("sub    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  647.     case ADC_CIO:printf("subc    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  648.     case AND:    printf("and    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  649.     case IOR:    printf("or    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  650.     case XOR:    printf("xor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  651.     case ANDC:    printf("andn    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  652.     case EQV:    printf("xnor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  653.     case NAND:    printf("nand    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  654.     case NOR:    printf("nor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  655.     case LSHIFTR:printf("srl    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  656.     case ASHIFTR:printf("sra    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  657.     case SHIFTL:printf("sll    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  658.     case CPEQ:    printf("cpeq    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  659.     case CPGE:    printf("cpge    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  660.     case CPGEU:    printf("cpgeu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  661.     case CPGT:    printf("cpgt    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  662.     case CPGTU:    printf("cpgtu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  663.     case CPLE:    printf("cple    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  664.     case CPLEU:    printf("cpleu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  665.     case CPLT:    printf("cplt    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  666.     case CPLTU:    printf("cpltu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  667.     case CPNEQ:    printf("cpneq    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  668.     case MUL:
  669.       printf("multiply    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  670.       break;      
  671. #elif M68000
  672.     case COPY:
  673.       if (IMMEDIATE_P(s1))
  674.     {
  675.       if ((signed_word) IMMEDIATE_VAL(s1) >= -128
  676.           && (signed_word) IMMEDIATE_VAL(s1) < 128)
  677.         {
  678.           printf("moveq    #%ld,%s", IMMEDIATE_VAL(s1),NAME(d));
  679.           break;
  680.         }
  681.     }
  682.       printf("movel    %s,%s",NAME(s1),NAME(d));
  683.       break;
  684.     case EXCHANGE:
  685.       printf("exgl    %s,%s",NAME(s2),NAME(d));break;
  686.     case ADD_CO:
  687.       if (IMMEDIATE_P(s2)
  688.       && IMMEDIATE_VAL(s2) >= 1 && IMMEDIATE_VAL(s2) <= 8)
  689.     printf("addql    %s,%s",NAME(s2),NAME(d));
  690.       else
  691.     printf("addl    %s,%s",NAME(s2),NAME(d));
  692.       break;
  693.     case ADD_CIO:
  694.       printf("addxl    %s,%s",NAME(s2),NAME(d));break;
  695.     case SUB:
  696.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  697.     printf("notl    %s",NAME(d));
  698.       else abort();
  699.       break;
  700.     case SUB_CO:
  701.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == 0)
  702.     printf("negl    %s",NAME(d));
  703.       else if (IMMEDIATE_P(s2)
  704.            && IMMEDIATE_VAL(s2) >= 1 && IMMEDIATE_VAL(s2) <= 8)
  705.     printf("subql    %s,%s",NAME(s2),NAME(d));
  706.       else
  707.     printf("subl    %s,%s",NAME(s2),NAME(d));
  708.       break;
  709.     case SUB_CIO:
  710.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == 0)
  711.     printf("negxl    %s",NAME(d));
  712.       else
  713.     printf("subxl    %s,%s",NAME(s2),NAME(d));
  714.       break;
  715.     case AND:
  716.       printf("andl    %s,%s",NAME(s2),NAME(d));break;
  717.     case IOR:
  718.       printf("orl    %s,%s",NAME(s2),NAME(d));break;
  719.     case XOR:
  720.       printf("eorl    %s,%s",NAME(s2),NAME(d));break;
  721.     case LSHIFTR_CO:
  722.       printf("lsrl    %s,%s",NAME(s2),NAME(d));break;
  723.     case ASHIFTR_CO:
  724.       printf("asrl    %s,%s",NAME(s2),NAME(d));break;
  725.     case SHIFTL_CO:
  726.       printf("lsll    %s,%s",NAME(s2),NAME(d));break;
  727.     case ROTATEL_CO:
  728.       printf("roll    %s,%s",NAME(s2),NAME(d));break;
  729.     case ROTATEXL_CIO:
  730.       printf("roxll    %s,%s",NAME(s2),NAME(d));break;
  731.     case MUL:
  732.       printf("mulsl    %s,%s",NAME(s2),NAME(d));break;      
  733. #elif I386
  734.     case COPY:
  735.       printf("movl    %s,%s",NAME(s1),NAME(d));break;
  736.     case EXCHANGE:
  737.       printf("xchgl    %s,%s",NAME(s2),NAME(d));break;
  738.     case ADD:
  739.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) == 1)
  740.     printf("incl    %s",NAME(d));
  741.       else abort();
  742.       break;
  743.     case ADD_CO:
  744.       printf("addl    %s,%s",NAME(s2),NAME(d));break;
  745.     case ADD_CIO:
  746.       printf("adcl    %s,%s",NAME(s2),NAME(d));break;
  747.     case SUB:
  748.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) == 1)
  749.     printf("decl    %s",NAME(d));
  750.       else if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  751.     printf("notl    %s",NAME(d));
  752.       else abort();
  753.       break;
  754.     case SUB_CO:
  755.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == 0)
  756.     printf("negl    %s",NAME(d));
  757.       else
  758.     printf("subl    %s,%s",NAME(s2),NAME(d));
  759.       break;
  760.     case SUB_CIO:
  761.       printf("sbbl    %s,%s",NAME(s2),NAME(d));break;
  762.     case CMP:
  763.       printf("cmpl    %s,%s",NAME(s2),NAME(s1));break;
  764.     case AND_RC:
  765.       printf("andl    %s,%s",NAME(s2),NAME(d));break;
  766.     case IOR_RC:
  767.       printf("orl    %s,%s",NAME(s2),NAME(d));break;
  768.     case XOR_RC:
  769.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x80 < 0x100)
  770.     printf("xorb    $%d,%s",IMMEDIATE_VAL(s2),NAME(d));
  771.       else
  772.     printf("xorl    %s,%s",NAME(s2),NAME(d));
  773.       break;
  774.     case LSHIFTR_CO:
  775.       printf("shrl    %s,%s",NAME(s2),NAME(d));break;
  776.     case ASHIFTR_CO:
  777.       printf("sarl    %s,%s",NAME(s2),NAME(d));break;
  778.     case SHIFTL_CO:
  779.       printf("shll    %s,%s",NAME(s2),NAME(d));break;
  780.     case ROTATEL_CO:
  781.       printf("roll    %s,%s",NAME(s2),NAME(d));break;
  782.     case ROTATEXL_CIO:
  783.       printf("rlcl    %s,%s",NAME(s2),NAME(d));break;
  784.     case COMCY:
  785.       printf("cmc");break;
  786.     case MUL:
  787.       printf("imull    %s,%s",NAME(s2),NAME(d));break;      
  788. #elif PYR
  789.     case COPY:
  790.       printf("movw    %s,%s",NAME(s1),NAME(d));break;
  791.     case EXCHANGE:
  792.       printf("xchw    %s,%s",NAME(s2),NAME(d));break;
  793.     case ADD:
  794.       printf("mova    0x%x(%s),%s",IMMEDIATE_VAL(s2),NAME(s1),NAME(d));
  795.       break;
  796.     case ADD_CO:
  797.       printf("addw    %s,%s",NAME(s2),NAME(d));break;
  798.     case ADD_CIO:
  799.       printf("addwc    %s,%s",NAME(s2),NAME(d));break;
  800.     case ADC_CO:
  801.       printf("subw    %s,%s",NAME(s2),NAME(d));break;
  802.     case ADC_CIO:
  803.       printf("subwb    %s,%s",NAME(s2),NAME(d));break;
  804.     case AND_CC:
  805.       printf("andw    %s,%s",NAME(s2),NAME(d));break;
  806.     case IOR_CC:
  807.       printf("orw    %s,%s",NAME(s2),NAME(d));break;
  808.     case XOR_CC:
  809.       printf("xorw    %s,%s",NAME(s2),NAME(d)); break;
  810.     case ANDC_CC:
  811.       printf("bicw    %s,%s",NAME(s2),NAME(d)); break;
  812.     case LSHIFTR_CO:
  813.       printf("lshrw    %s,%s",NAME(s2),NAME(d));break;
  814.     case ASHIFTR_CO:
  815.       printf("ashrw    %s,%s",NAME(s2),NAME(d));break;
  816.     case SHIFTL_CO:
  817.       printf("lshlw    %s,%s",NAME(s2),NAME(d));break;
  818.     case MUL:
  819.       printf("mulw    %s,%s",NAME(s2),NAME(d));break;      
  820. #else
  821. #error no assembler output code for this CPU
  822. #endif
  823.     default:abort();
  824.     }
  825.   printf("\n");
  826. }
  827.  
  828. word tvalues[0x100];
  829.  
  830. /* TEST_SETS contains sets of input values and corresponding goal value used
  831.    to test the correctness of a sequence.  N_TEST_SETS says how many sets
  832.    are defined.  */
  833. word *test_sets;
  834. int n_test_sets;
  835.  
  836. word test_operands[] =
  837. {
  838.   0,
  839.   1,
  840.   -1,
  841.   -2,
  842.   VALUE_MIN_SIGNED,
  843.   VALUE_MAX_SIGNED,
  844.   VALUE_MIN_SIGNED + 1,
  845.   VALUE_MAX_SIGNED - 1,
  846. };
  847. #define N_TEST_OPERANDS (sizeof(test_operands)/sizeof(test_operands[0]))
  848.  
  849. void
  850. init_test_sets()
  851. {
  852.   unsigned int loop_vars[8];
  853.   int pc, i, j;
  854.   word *test_set;
  855.   const int arity = goal_function_arity;
  856.   word (*eval) (const word *) = eval_goal_function;
  857.  
  858.   if (sizeof (loop_vars) / sizeof (loop_vars[0]) <= arity)
  859.     abort ();
  860.  
  861.   /* Allocate enough space in TEST_SETS for all combinations of TEST_OPERANDS
  862.      and an additional 10,000 random test sets.  */
  863.   {
  864.     static int n_words;
  865.  
  866.     j = 1 + arity;
  867.     for (i = arity - 1; i >= 0; i--)
  868.       j *= N_TEST_OPERANDS;
  869.  
  870.     j += (1 + arity) * 10000;
  871.  
  872.     if (n_words < j)
  873.       {
  874.     test_sets = (n_words == 0
  875.              ? (word *) xmalloc (sizeof (word) * j)
  876.              : (word *) xrealloc (test_sets, sizeof (word) * j));
  877.     n_words = j;
  878.       }
  879.   }
  880.  
  881.   test_set = test_sets;
  882.   j = 0;
  883.  
  884.   /* Start with all combinations of operands from TEST_OPERANDS.  */
  885.   for (i = arity - 1; i >= 0; i--)
  886.     loop_vars[i] = 0;
  887.   for (;;)
  888.     {
  889.       for (i = arity - 1; i >= 0; i--)
  890.     tvalues[i] = *test_set++ = test_operands[loop_vars[i]];
  891.  
  892.       /* Get the desired value for the current operand values.  */
  893.       *test_set++ = (*eval)(tvalues);
  894.       j++;
  895.  
  896.     next:
  897.       /* General loop control.  This implements ARITY loops using induction
  898.      variables in loop_vars[0] through loop_vars[ARITY - 1].  */
  899.       i = 0;
  900.       loop_vars[i] = (loop_vars[i] + 1) % N_TEST_OPERANDS;
  901.       while (loop_vars[i] == 0)
  902.     {
  903.       i++;
  904.       if (i >= arity)
  905.         goto random;
  906.       loop_vars[i] = (loop_vars[i] + 1) % N_TEST_OPERANDS;
  907.     }
  908.     }
  909.  
  910.   /* Now add the additional random test sets.  */
  911.  random:  
  912.   for (i = 9999; i >= 0; i--)
  913.     {
  914.       for (pc = arity - 1; pc >= 0; pc--)
  915.     tvalues[pc] = *test_set++ = random_word();
  916. #ifdef UDIV_WITH_SDIV
  917.       if (tvalues[1] == 0)
  918.     {
  919.       test_set -= arity;
  920.       continue;
  921.     }
  922. #endif
  923.       *test_set++ = (*eval)(tvalues);
  924.       j++;
  925.     }
  926.  
  927.   n_test_sets = j;
  928. }
  929.  
  930. /* Test the correctness of a sequence in SEQUENCE[0] through
  931.    SEQUENCE[N_INSNS - 1].  */
  932.  
  933. void
  934. test_sequence(insn_t *sequence, int n_insns)
  935. {
  936.   int pc;
  937.   int i, j;
  938.   word *test_set = test_sets;
  939.   const int arity = goal_function_arity;
  940.  
  941.   /* Test each of the precomputed values.  */
  942.   for (j = n_test_sets; j > 0; j--)
  943.     {
  944.       /* Update the tvalues array in each iteration, as execution of the
  945.      sequence might clobber the values.  (On 2-operand machines.)  */
  946.       for (i = arity - 1; i >= 0; i--)
  947.     tvalues[i] = *test_set++;
  948.  
  949.       /* Execute the synthesised sequence for the current operand values.  */
  950.       run_program (sequence, n_insns, tvalues);
  951.       if (tvalues[sequence[n_insns - 1].d] != *test_set++)
  952.     {
  953.       /* Adaptively rearrange the order of the tests.  This set of test
  954.          values is better than all that preceed it.  The optimal ordering
  955.          changes with the search space.  */
  956.       if ((j = n_test_sets - j) != 0)
  957.         {
  958.           int k = j >> 1;
  959.           j *= (arity + 1);
  960.           k *= (arity + 1);
  961.           for (i = 0; i <= arity; i++)
  962.         {
  963.           word t = test_sets[j + i];
  964.           test_sets[j + i] = test_sets[k + i];
  965.           test_sets[k + i] = t;
  966.         }
  967.         }
  968.       return;
  969.     }
  970.     }
  971.  
  972.   /* The tests passed.  Print the instruction sequence.  */
  973.   if (success == 0)
  974.     printf("\n");
  975.   success++;
  976.  
  977.   printf("%d:", success);
  978.   for (pc = 0; pc < n_insns; pc++)
  979.     {
  980.       insn_t insn;
  981.  
  982.       insn = sequence[pc];
  983.       if (flag_output_assembler)
  984.     output_assembler(insn);
  985.       else
  986.     {
  987.       if (insn.opcode == CMP)
  988.         printf("\t%s(", GET_INSN_NAME(insn.opcode));
  989.       else
  990.         printf("\tr%u:=%s(", insn.d, GET_INSN_NAME(insn.opcode));
  991.       if (IMMEDIATE_P(insn.s1))
  992.         {
  993.           if ((signed_word) IMMEDIATE_VAL(insn.s1) >= 10
  994.           || (signed_word) IMMEDIATE_VAL(insn.s1) <= -10)
  995.         printf("0x%lx", IMMEDIATE_VAL(insn.s1));
  996.           else
  997.         printf("%ld", IMMEDIATE_VAL(insn.s1));
  998.         }
  999.       else
  1000.         printf("r%u", insn.s1);
  1001.  
  1002.       if (!UNARY_OPERATION(insn))
  1003.         {
  1004.           if (IMMEDIATE_P(insn.s2))
  1005.         {
  1006.           if ((signed_word) IMMEDIATE_VAL(insn.s2) >= 10
  1007.               || (signed_word) IMMEDIATE_VAL(insn.s2) <= -10)
  1008.             printf(",0x%lx", IMMEDIATE_VAL(insn.s2));
  1009.           else
  1010.             printf(",%ld", IMMEDIATE_VAL(insn.s2));
  1011.         }
  1012.           else
  1013.         printf(",r%u", insn.s2);
  1014.         }
  1015.       printf(")\n");
  1016.     }
  1017.     }
  1018.   fflush(stdout);
  1019. }
  1020.  
  1021.  
  1022. /* Recursively investigate all possible instruction sequences for the
  1023.    current target.
  1024.  
  1025.    SEQUENCE contains the instructions defined so far.
  1026.  
  1027.    N_INSNS is the number of instructions, including the one we will
  1028.    generate this time, in SEQUENCE.
  1029.  
  1030.    VALUES contains the values in register 0..N_VALUES.
  1031.  
  1032.    N_VALUES is the number of registers that have been assigned values by
  1033.    the insns so far.
  1034.  
  1035.    GOAL_VALUE is the value we aim at, when the sequence is ready.
  1036.  
  1037.    ALLOWED_COST is the maximum allowed cost of the remaining sequence.
  1038.  
  1039.    CY_IN is the carry flag.  It is negative if no instruction has yet
  1040.    defined it (this to pruning the search tree), and otherwise takes the
  1041.    values 0 or 1 according to the conventions of the current target.
  1042.  
  1043.    PRUNE_HINT contains flags to assist pruning of the search tree.  */
  1044.  
  1045. #if SPARC || RS6000 || M88000 || AM29K
  1046. void
  1047. synth(insn_t *sequence,
  1048.       int n_insns,
  1049.       word *values,
  1050.       int n_values,
  1051.       word goal_value,
  1052.       int allowed_cost,
  1053.       int ci,
  1054.       int prune_hint)
  1055. {
  1056.   int s1, s2;
  1057.   word v, r1, r2;
  1058.   int co;
  1059.   int last_dest;
  1060.  
  1061. #ifdef TIMING
  1062.   int time_start = cputime();
  1063. #endif
  1064.  
  1065.   if (n_insns > 0)
  1066.     last_dest = sequence[n_insns - 1].d;
  1067.   else
  1068.     last_dest = -1;
  1069.  
  1070.   /* Binary operations with carry-in.  */
  1071.   if (ci >= 0 && flag_use_carry)
  1072.     {
  1073.       for (s1 = n_values - 1; s1 >= 0; s1--)
  1074.     {
  1075.       r1 = values[s1];
  1076.       for (s2 = s1 - 1; s2 >= 0; s2--)
  1077.         {
  1078.           r2 = values[s2];
  1079.  
  1080.           if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
  1081.         {
  1082.           /* We are in a leaf node.  CY was not set (to 0, 1 or to
  1083.              a data dependent value) by the previous insn.
  1084.  
  1085.              So one of the input operands has to be the result
  1086.              operand of the previous insn for that insn to be
  1087.              meaningful.  */
  1088.           if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
  1089.             continue;
  1090.         }
  1091.  
  1092. #if SPARC || RS6000 || M88000 || AM29K
  1093.           /* sparc:        addxcc
  1094.          rs6000:    ae
  1095.          m88000:    addu.cio
  1096.          am29k:        addc */
  1097.           PERFORM_ADD_CIO(v, co, r1, r2, ci);
  1098.           RECURSE(ADD_CIO, s1, s2, CY_JUST_SET);
  1099. #endif
  1100. #if SPARC || M88000
  1101.           /* sparc:        addx
  1102.          m88000:    addu.ci */
  1103.           PERFORM_ADD_CI(v, co, r1, r2, ci);
  1104.           RECURSE(ADD_CI, s1, s2, prune_hint & ~CY_JUST_SET);
  1105. #endif
  1106. #if SPARC
  1107.           /* sparc:        subxcc */
  1108.           PERFORM_SUB_CIO(v, co, r1, r2, ci);
  1109.           RECURSE(SUB_CIO, s1, s2, CY_JUST_SET);
  1110.           PERFORM_SUB_CIO(v, co, r2, r1, ci);
  1111.           RECURSE(SUB_CIO, s2, s1, CY_JUST_SET);
  1112. #endif
  1113. #if SPARC
  1114.           /* sparc:        subx */
  1115.           PERFORM_SUB_CI(v, co, r1, r2, ci);
  1116.           RECURSE(SUB_CI, s1, s2, prune_hint & ~CY_JUST_SET);
  1117.           PERFORM_SUB_CI(v, co, r2, r1, ci);
  1118.           RECURSE(SUB_CI, s2, s1, prune_hint & ~CY_JUST_SET);
  1119. #endif
  1120. #if RS6000 || M88000 || AM29K
  1121.           /* rs6000:    sfe
  1122.          m88000:    subu.cio
  1123.          am29k:        subc */
  1124.           PERFORM_ADC_CIO(v, co, r1, r2, ci);
  1125.           RECURSE(ADC_CIO, s1, s2, CY_JUST_SET);
  1126.           PERFORM_ADC_CIO(v, co, r2, r1, ci);
  1127.           RECURSE(ADC_CIO, s2, s1, CY_JUST_SET);
  1128. #endif
  1129. #if M88000
  1130.           /* m88000:    subu.ci */
  1131.           PERFORM_ADC_CI(v, co, r1, r2, ci);
  1132.           RECURSE(ADC_CI, s1, s2, prune_hint & ~CY_JUST_SET);
  1133.           PERFORM_ADC_CI(v, co, r2, r1, ci);
  1134.           RECURSE(ADC_CI, s2, s1, prune_hint & ~CY_JUST_SET);
  1135. #endif
  1136.         }
  1137.     }
  1138.     }
  1139.  
  1140.   /* Binary operations without carry-in.  */
  1141.   for (s1 = n_values - 1; s1 >= 0; s1--)
  1142.     {
  1143.       r1 = values[s1];
  1144.       for (s2 = s1 - 1; s2 >= 0; s2--)
  1145.     {
  1146.       r2 = values[s2];
  1147.  
  1148.       if (allowed_cost <= 1)
  1149.         {
  1150.           /* We are in a leaf node.
  1151.  
  1152.          So one of the input operands has to be the result operand
  1153.          of the previous insn for that insn to be meaningful.  */
  1154.           if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
  1155.         continue;
  1156.         }
  1157.  
  1158. #ifdef DM
  1159.       PERFORM_UMULWIDEN_HI(v, co, r1, r2, ci);
  1160.       RECURSE(UMULWIDEN_HI, s1, s2, prune_hint & ~CY_JUST_SET);
  1161. #endif
  1162. #if defined (DM) || defined (MM)
  1163.       PERFORM_MUL(v, co, r1, r2, ci);
  1164.       RECURSE(MUL, s1, s2, prune_hint & ~CY_JUST_SET);
  1165. #endif
  1166. #ifdef UDIV_WITH_SDIV
  1167.       PERFORM_SDIV (v, co, r1, r2, ci);
  1168.       RECURSE(SDIV, s1, s2, prune_hint & ~CY_JUST_SET);
  1169. #endif
  1170. #if SPARC || RS6000 || M88000 || AM29K
  1171.       /* sparc:    addcc
  1172.          rs6000:    a
  1173.          m88000:    addu.co
  1174.          am29k:    add */
  1175.       PERFORM_ADD_CO(v, co, r1, r2, ci);
  1176.       RECURSE(ADD_CO, s1, s2, CY_JUST_SET);
  1177. #endif
  1178. #if SPARC || RS6000 || M88000
  1179.       /* sparc:    add
  1180.          rs6000:    cax
  1181.          m88000:    addu */
  1182.       PERFORM_ADD(v, co, r1, r2, ci);
  1183.       RECURSE(ADD, s1, s2, prune_hint & ~CY_JUST_SET);
  1184. #endif
  1185. #if SPARC
  1186.       /* sparc:    subcc */
  1187.       PERFORM_SUB_CO(v, co, r1, r2, ci);
  1188.       RECURSE(SUB_CO, s1, s2, CY_JUST_SET);
  1189.       PERFORM_SUB_CO(v, co, r2, r1, ci);
  1190.       RECURSE(SUB_CO, s2, s1, CY_JUST_SET);
  1191. #endif
  1192. #if SPARC || M88000
  1193.       /* sparc:    sub
  1194.          m88000:    subu */
  1195.       PERFORM_SUB(v, co, r1, r2, ci);
  1196.       RECURSE(SUB, s1, s2, prune_hint & ~CY_JUST_SET);
  1197.       PERFORM_SUB(v, co, r2, r1, ci);
  1198.       RECURSE(SUB, s2, s1, prune_hint & ~CY_JUST_SET);
  1199. #endif
  1200. #if RS6000 || M88000 || AM29K
  1201.       /* rs6000:    sf
  1202.          m88000:    subu.co
  1203.          am29k:    sub */
  1204.       PERFORM_ADC_CO(v, co, r1, r2, ci);
  1205.       RECURSE(ADC_CO, s1, s2, CY_JUST_SET);
  1206.       PERFORM_ADC_CO(v, co, r2, r1, ci);
  1207.       RECURSE(ADC_CO, s2, s1, CY_JUST_SET);
  1208. #endif
  1209. #if SPARC || RS6000 || M88000 || AM29K
  1210.       PERFORM_AND(v, co, r1, r2, ci);
  1211.       RECURSE(AND, s1, s2, prune_hint & ~CY_JUST_SET);
  1212.  
  1213.       PERFORM_IOR(v, co, r1, r2, ci);
  1214.       RECURSE(IOR, s1, s2, prune_hint & ~CY_JUST_SET);
  1215.  
  1216.       PERFORM_XOR(v, co, r1, r2, ci);
  1217.       RECURSE(XOR, s1, s2, prune_hint & ~CY_JUST_SET);
  1218.  
  1219.       PERFORM_ANDC(v, co, r1, r2, ci);
  1220.       RECURSE(ANDC, s1, s2, prune_hint & ~CY_JUST_SET);
  1221.       PERFORM_ANDC(v, co, r2, r1, ci);
  1222.       RECURSE(ANDC, s2, s1, prune_hint & ~CY_JUST_SET);
  1223. #endif
  1224. #if SPARC || RS6000 || M88000
  1225.       PERFORM_IORC(v, co, r1, r2, ci);
  1226.       RECURSE(IORC, s1, s2, prune_hint & ~CY_JUST_SET);
  1227.       PERFORM_IORC(v, co, r2, r1, ci);
  1228.       RECURSE(IORC, s2, s1, prune_hint & ~CY_JUST_SET);
  1229. #endif
  1230. #if SPARC || RS6000 || M88000 || AM29K
  1231.       PERFORM_EQV(v, co, r1, r2, ci);
  1232.       RECURSE(EQV, s1, s2, prune_hint & ~CY_JUST_SET);
  1233. #endif
  1234. #if RS6000 || AM29K
  1235.       PERFORM_NAND(v, co, r1, r2, ci);
  1236.       RECURSE(NAND, s1, s2, prune_hint & ~CY_JUST_SET);
  1237.  
  1238.       PERFORM_NOR(v, co, r1, r2, ci);
  1239.       RECURSE(NOR, s1, s2, prune_hint & ~CY_JUST_SET);
  1240. #endif
  1241. #if RS6000 && !defined (AVOID_DOZ)
  1242.       PERFORM_DOZ(v, co, r1, r2, ci);
  1243.       RECURSE(DOZ, s1, s2, prune_hint & ~CY_JUST_SET);
  1244.       PERFORM_DOZ(v, co, r2, r1, ci);
  1245.       RECURSE(DOZ, s2, s1, prune_hint & ~CY_JUST_SET);
  1246. #endif
  1247. #if AM29K
  1248.       PERFORM_CPEQ(v, co, r1, r2, ci);
  1249.       RECURSE(CPEQ, s1, s2, prune_hint & ~CY_JUST_SET);
  1250.       PERFORM_CPGE(v, co, r1, r2, ci);
  1251.       RECURSE(CPGE, s1, s2, prune_hint & ~CY_JUST_SET);
  1252.       PERFORM_CPGEU(v, co, r1, r2, ci);
  1253.       RECURSE(CPGEU, s1, s2, prune_hint & ~CY_JUST_SET);
  1254.       PERFORM_CPGT(v, co, r1, r2, ci);
  1255.       RECURSE(CPGT, s1, s2, prune_hint & ~CY_JUST_SET);
  1256.       PERFORM_CPGTU(v, co, r1, r2, ci);
  1257.       RECURSE(CPGTU, s1, s2, prune_hint & ~CY_JUST_SET);
  1258.       PERFORM_CPLE(v, co, r1, r2, ci);
  1259.       RECURSE(CPLE, s1, s2, prune_hint & ~CY_JUST_SET);
  1260.       PERFORM_CPLEU(v, co, r1, r2, ci);
  1261.       RECURSE(CPLEU, s1, s2, prune_hint & ~CY_JUST_SET);
  1262.       PERFORM_CPLT(v, co, r1, r2, ci);
  1263.       RECURSE(CPLT, s1, s2, prune_hint & ~CY_JUST_SET);
  1264.       PERFORM_CPLTU(v, co, r1, r2, ci);
  1265.       RECURSE(CPLTU, s1, s2, prune_hint & ~CY_JUST_SET);
  1266.       PERFORM_CPNEQ(v, co, r1, r2, ci);
  1267.       RECURSE(CPNEQ, s1, s2, prune_hint & ~CY_JUST_SET);
  1268. #endif
  1269. #if M88000
  1270.       PERFORM_CMPPAR (v, co, r1, r2, ci);
  1271.       RECURSE(CMPPAR, s1, s2, prune_hint & ~CY_JUST_SET);
  1272.       PERFORM_CMPPAR (v, co, r2, r1, ci);
  1273.       RECURSE(CMPPAR, s2, s1, prune_hint & ~CY_JUST_SET);
  1274. #endif
  1275.     }
  1276.     }
  1277.  
  1278.   /* Unary operations with carry-in.  */
  1279.   if (ci >= 0 && flag_use_carry)
  1280.     {
  1281.       for (s1 = n_values - 1; s1 >= 0; s1--)
  1282.     {
  1283.       r1 = values[s1];
  1284.  
  1285.       if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
  1286.         {
  1287.           /* We are in a leaf node and CY was not set (to 1 or to a
  1288.          data dependent value) by the previous insn.
  1289.  
  1290.          The input operand has to be the result operand of the
  1291.          previous insn for that insn to be meaningful.  */
  1292.           if (last_dest >= 0 && s1 != last_dest)
  1293.         continue;
  1294.         }
  1295.  
  1296. #if SPARC || RS6000 || M88000 || AM29K
  1297.       /* d,cy = 2*r1 + cy
  1298.          sparc:        addxcc    s1,s1,d
  1299.          rs6000:    ae    d,s1,s1
  1300.          m88000:    addu.cio d,s1,s1
  1301.          am29k:        addc    d,s1,s1 */
  1302.       PERFORM_ADD_CIO(v, co, r1, r1, ci);
  1303.       RECURSE(ADD_CIO, s1, s1, CY_JUST_SET);
  1304. #endif
  1305. #if SPARC || M88000 
  1306.       /* d,cy = 2*r1 + cy
  1307.          sparc:        addx    s1,s1,d
  1308.          m88000:    addu.ci    d,s1,s1  */
  1309.       PERFORM_ADD_CI(v, co, r1, r1, ci);
  1310.       RECURSE(ADD_CI, s1, s1, prune_hint & ~CY_JUST_SET);
  1311. #endif
  1312. #if SPARC || RS6000 || M88000 || AM29K
  1313.       /* d,cy = r1 + cy - 1
  1314.          sparc:    addxcc    s1,-1,d
  1315.          rs6000:    ame    d,s1
  1316.          m88000:    subu.cio d,s1,r0
  1317.          am29k:    subc    d,s1,0 */
  1318.       PERFORM_ADD_CIO(v, co, r1, VALUE(-1), ci);
  1319.       RECURSE(ADD_CIO, s1, CNST(-1), CY_JUST_SET);
  1320. #endif
  1321. #if SPARC || RS6000 || M88000 || AM29K
  1322.       /* d,cy = r1 + cy
  1323.          sparc:    addxcc    s1,0,d
  1324.          rs6000:    aze    d,s1
  1325.          m88000:    addu.cio d,s1,r0
  1326.          am29k:    addc    d,s1,0 */
  1327.       PERFORM_ADD_CIO(v, co, r1, VALUE(0), ci);
  1328.       RECURSE(ADD_CIO, s1, CNST(0), CY_JUST_SET);
  1329. #endif
  1330. #if SPARC
  1331.       /* d,cy = 0 - r1 - cy
  1332.          sparc:     subxcc    %g0,s1,d */
  1333.       PERFORM_SUB_CIO(v, co, VALUE(0), r1, ci);
  1334.       RECURSE(SUB_CIO, CNST(0), s1, CY_JUST_SET);
  1335. #endif
  1336. #if RS6000
  1337.       /* d,cy = -1 + ~r1 + cy
  1338.          rs6000:    sfme    d,s1 */
  1339.       PERFORM_ADC_CIO(v, co, VALUE(-1), r1, ci);
  1340.       RECURSE(ADC_CIO, CNST(-1), s1, CY_JUST_SET);
  1341. #endif
  1342. #if RS6000 || M88000 || AM29K
  1343.       /* d,cy = ~r1 + cy
  1344.          m88000:    subu.cio d,r0,s1
  1345.          rs6000:    sfze    d,s1
  1346.          am29k:    subrc    d,s1,0 */
  1347.       PERFORM_ADC_CIO(v, co, VALUE(0), r1, ci);
  1348.       RECURSE(ADC_CIO, CNST(0), s1, CY_JUST_SET);
  1349. #endif
  1350.     }
  1351.     }
  1352.  
  1353.   /* Unary operations without carry-in.  */
  1354.   for (s1 = n_values - 1; s1 >= 0; s1--)
  1355.     {
  1356.       r1 = values[s1];
  1357.  
  1358.       if (allowed_cost <= 1)
  1359.     {
  1360.       /* We are in a leaf node.
  1361.  
  1362.          The input operand has to be the result operand of the
  1363.          previous insns for that insn to be meaningful.  */
  1364.       if (last_dest >= 0 && s1 != last_dest)
  1365.         continue;
  1366.     }
  1367.  
  1368. #ifdef DM
  1369.       PERFORM_INVDIV(v, co, r1, ci);
  1370.       RECURSE(INVDIV, s1, 0, prune_hint & ~CY_JUST_SET);
  1371.  
  1372.       PERFORM_INVMOD(v, co, r1, ci);
  1373.       RECURSE(INVMOD, s1, 0, prune_hint & ~CY_JUST_SET);
  1374. #endif
  1375. #if SPARC || RS6000 || M88000 || AM29K
  1376.       /* d,cy = 2*r1
  1377.      sparc:        addcc    s1,s1,d
  1378.      rs6000:    a    d,s1,s1
  1379.      m88000:    addu.co    d,s1,s1
  1380.      am29k:        add    d,s1,s1 */
  1381.       PERFORM_ADD_CO(v, co, r1, r1, ci);
  1382.       RECURSE(ADD_CO, s1, s1, CY_JUST_SET);
  1383. #endif
  1384. #if SPARC || RS6000 || M88000 || AM29K
  1385.       /* d = r1 & 1
  1386.      sparc:        and    s1,1,d
  1387.      rs6000:    rlinm    d,s1,0,31,31
  1388.      m88000:    mask    d,s1,1
  1389.      am29k:        and    d,s1,1 */
  1390.       PERFORM_AND(v, co, r1, VALUE(1), ci);
  1391.       RECURSE(AND, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1392. #endif
  1393. #if RS6000 || M88000
  1394.       /* d = r1 & 0x80000000
  1395.      rs6000:    rlinm    d,s1,0,0,0
  1396.      m88000:    mask.u    d,s1,0x8000 */
  1397.       PERFORM_AND(v, co, r1, VALUE_MIN_SIGNED, ci);
  1398.       RECURSE(AND, s1, CNST_0x80000000, prune_hint & ~CY_JUST_SET);
  1399.  
  1400.       /* d = r1 & 0x7fffffff
  1401.      rs6000:    rlinm    d,s1,0,1,31
  1402.      m88000:    and.u    d,s1,0x7fff */
  1403.       PERFORM_AND(v, co, r1, VALUE_MAX_SIGNED, ci);
  1404.       RECURSE(AND, s1, CNST_0x7FFFFFFF, prune_hint & ~CY_JUST_SET);
  1405. #endif
  1406. #if RS6000 || M88000
  1407.       PERFORM_XOR(v, co, r1, VALUE_MIN_SIGNED, ci);
  1408.       RECURSE(XOR, s1, CNST_0x80000000, prune_hint & ~CY_JUST_SET);
  1409.  
  1410.       PERFORM_IOR(v, co, r1, VALUE_MIN_SIGNED, ci);
  1411.       RECURSE(IOR, s1, CNST_0x80000000, prune_hint & ~CY_JUST_SET);
  1412. #endif
  1413. #if SPARC || RS6000 || M88000 || AM29K
  1414.       /* d = r1 ^ 1
  1415.      sparc:        xor    s1,1,d
  1416.      rs6000:    xoril    d,s1,1
  1417.      m88000:    xor    d,s1,1
  1418.      am29k:        xor    d,s1,1 */
  1419.       PERFORM_XOR(v, co, r1, VALUE(1), ci);
  1420.       RECURSE(XOR, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1421. #endif
  1422. #if SPARC || RS6000 || M88000 || AM29K
  1423.       /* d = ~r1
  1424.      sparc:        xnor    %g0,s1,d
  1425.      rs6000:    nand    d,s1,s1
  1426.      m88000:    xor.c    d,s1,r0
  1427.      am29k:        nand    d,s1,s1 */
  1428.       PERFORM_SUB(v, co, VALUE(-1), r1, ci);
  1429.       RECURSE(SUB, CNST(-1), s1, prune_hint & ~CY_JUST_SET);
  1430. #endif
  1431. #if RS6000
  1432.       /* d,cy = -1 + ~r1 (i.e. one's complement and set carry.)
  1433.      rs6000:    sfi    d,s1,-1 */
  1434.       PERFORM_ADC_CO(v, co, VALUE(-1), r1, ci);
  1435.       RECURSE(ADC_CO, CNST(-1), s1, CY_JUST_SET | CY_1);
  1436. #endif
  1437. #if SPARC || RS6000 || AM29K
  1438.       /* d,cy = r1 + 1
  1439.      sparc:        addcc    s1,1,d
  1440.      rs6000:    ai    d,s1,1
  1441.      am29k:        add    d,s1,1 */
  1442.       PERFORM_ADD_CO(v, co, r1, VALUE(1), ci);
  1443.       RECURSE(ADD_CO, s1, CNST(1), CY_JUST_SET);
  1444. #endif
  1445. #if SPARC || RS6000 || M88000
  1446.       /* d = r1 + 1
  1447.      sparc:        add    s1,1,d
  1448.      rs6000:    cal    d,1(s1)
  1449.      m88000:    addu    d,s1,1 */
  1450.       PERFORM_ADD(v, co, r1, VALUE(1), ci);
  1451.       RECURSE(ADD, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1452. #endif
  1453. #if 0 && RS6000 /* This has the same effect as a "xoriu". */
  1454.       /* d = r1 + 0x80000000
  1455.      rs6000:    cau    d,s1,0x8000 */
  1456.       PERFORM_ADD(v, co, r1, VALUE_MIN_SIGNED, ci);
  1457.       RECURSE(ADD, s1, CNST_0x80000000, CY_JUST_SET);
  1458. #endif
  1459. #if SPARC || RS6000 || AM29K /* not M88000 */
  1460.       /* d,cy = r1 + -1
  1461.      sparc:        addcc    s1,-1,d
  1462.      rs6000:    ai    d,s1,-1
  1463.      am29k:        sub    d,s1,1 */
  1464.       PERFORM_ADD_CO(v, co, r1, VALUE(-1), ci);
  1465.       RECURSE(ADD_CO, s1, CNST(-1), CY_JUST_SET);
  1466. #endif
  1467. #if SPARC
  1468.       /* d,cy = r1 - 1. [This isn't redundant, in spite we add -1 above.]
  1469.      sparc:        subcc    s1,1,d */
  1470.       PERFORM_SUB_CO(v, co, r1, VALUE(1), ci);
  1471.       RECURSE(SUB_CO, s1, CNST(1), CY_JUST_SET);
  1472. #endif
  1473. #if SPARC
  1474.       /* d,cy = -r1
  1475.      sparc:        subcc    %g0,s1,d */
  1476.       PERFORM_SUB_CO(v, co, VALUE(0), r1, ci);
  1477.       RECURSE(SUB_CO, CNST(0), s1, CY_JUST_SET);
  1478. #endif
  1479. #if SPARC || RS6000 || M88000
  1480.       /* d = -r1
  1481.      sparc:        sub    %g0,s1,d
  1482.      rs6000:    neg    d,s1
  1483.      m88000:    subu    d,r0,s1 */
  1484.       PERFORM_SUB(v, co, VALUE(0), r1, ci);
  1485.       RECURSE(SUB, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1486. #endif
  1487. #if RS6000 || M88000 || AM29K
  1488.       /* d,cy = -r1
  1489.      rs6000:    sf    d,s1,0
  1490.      m88000:    subu.co    d,r0,s1
  1491.      am29k:        subr    d,s1,0 */
  1492.       PERFORM_ADC_CO(v, co, VALUE(0), r1, ci);
  1493.       RECURSE(ADC_CO, CNST(0), s1, CY_JUST_SET);
  1494. #endif
  1495. #if RS6000
  1496.       /* d = abs(r1)
  1497.      rs6000:    abs    d,s1 */
  1498.       PERFORM_ABSVAL(v, co, r1, ci);
  1499.       RECURSE(ABSVAL, s1, 0, prune_hint & ~CY_JUST_SET);
  1500.  
  1501.       /* d = -abs(r1)
  1502.      rs6000:    nabs    d,s1 */
  1503.       PERFORM_NABSVAL(v, co, r1, ci);
  1504.       RECURSE(NABSVAL, s1, 0, prune_hint & ~CY_JUST_SET);
  1505. #endif
  1506. #if RS6000 && !defined (AVOID_DOZ)
  1507.       PERFORM_DOZ(v, co, VALUE(0), r1, ci);
  1508.       RECURSE(DOZ, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1509.       PERFORM_DOZ(v, co, VALUE(-1), r1, ci);
  1510.       RECURSE(DOZ, CNST(-1), s1, prune_hint & ~CY_JUST_SET);
  1511. #endif
  1512. #if SHIFTS
  1513.       {
  1514.     int cnt;
  1515.     for (cnt = 1; cnt < BITS_PER_WORD; cnt++)
  1516.       {
  1517. #if SPARC || RS6000 || M88000 || AM29K
  1518.         PERFORM_LSHIFTR(v, co, r1, VALUE(cnt), ci);
  1519.         RECURSE(LSHIFTR, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1520. #endif
  1521. #if SPARC || M88000 || AM29K
  1522.         PERFORM_ASHIFTR(v, co, r1, VALUE(cnt), ci);
  1523.         RECURSE(ASHIFTR, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1524. #endif
  1525. #if RS6000
  1526.         PERFORM_ASHIFTR_CON(v, co, r1, VALUE(cnt), ci);
  1527.         RECURSE(ASHIFTR_CON, s1, CNST(cnt), CY_JUST_SET);
  1528. #endif
  1529. #if SPARC || RS6000 || M88000 || AM29K
  1530.         PERFORM_SHIFTL(v, co, r1, VALUE(cnt), ci);
  1531.         RECURSE(SHIFTL, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1532. #endif
  1533. #if RS6000 || M88000
  1534.         PERFORM_ROTATEL(v, co, r1, VALUE(cnt), ci);
  1535.         RECURSE(ROTATEL, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1536. #endif
  1537.       }
  1538.       }
  1539. #else
  1540. #if SPARC || RS6000 || M88000 || AM29K
  1541.       PERFORM_LSHIFTR(v, co, r1, VALUE(1), ci);
  1542.       RECURSE(LSHIFTR, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1543. #endif
  1544. #if SPARC || M88000 || AM29K
  1545.       PERFORM_ASHIFTR(v, co, r1, VALUE(1), ci);
  1546.       RECURSE(ASHIFTR, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1547. #endif
  1548. #if RS6000
  1549.       PERFORM_ASHIFTR_CON(v, co, r1, VALUE(1), ci);
  1550.       RECURSE(ASHIFTR_CON, s1, CNST(1), CY_JUST_SET);
  1551. #endif
  1552. #if SPARC || RS6000 || M88000 || AM29K
  1553.       PERFORM_SHIFTL(v, co, r1, VALUE(1), ci);
  1554.       RECURSE(SHIFTL, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1555. #endif
  1556. #if RS6000 || M88000
  1557.       PERFORM_ROTATEL(v, co, r1, VALUE(1), ci);
  1558.       RECURSE(ROTATEL, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1559. #endif
  1560. #if SPARC || RS6000 || M88000 || AM29K
  1561.       PERFORM_LSHIFTR(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  1562.       RECURSE(LSHIFTR, s1, CNST(BITS_PER_WORD-1), prune_hint & ~CY_JUST_SET);
  1563. #endif
  1564. #if SPARC || M88000 || AM29K
  1565.       PERFORM_ASHIFTR(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  1566.       RECURSE(ASHIFTR, s1, CNST(BITS_PER_WORD-1), prune_hint & ~CY_JUST_SET);
  1567. #endif
  1568. #if RS6000
  1569.       PERFORM_ASHIFTR_CON(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  1570.       RECURSE(ASHIFTR_CON, s1, CNST(BITS_PER_WORD-1), CY_JUST_SET);
  1571. #endif
  1572. #if SHIFT16
  1573. #if SPARC || RS6000 || M88000 || AM29K
  1574.       PERFORM_LSHIFTR(v, co, r1, VALUE(16), ci);
  1575.       RECURSE(LSHIFTR, s1, CNST(16), prune_hint & ~CY_JUST_SET);
  1576. #endif
  1577. #if SPARC || M88000 || AM29K
  1578.       PERFORM_ASHIFTR(v, co, r1, VALUE(16), ci);
  1579.       RECURSE(ASHIFTR, s1, CNST(16), prune_hint & ~CY_JUST_SET);
  1580. #endif
  1581. #if RS6000
  1582.       PERFORM_ASHIFTR_CON(v, co, r1, VALUE(16), ci);
  1583.       RECURSE(ASHIFTR_CON, s1, CNST(16), CY_JUST_SET);
  1584. #endif
  1585. #if SPARC || RS6000 || M88000 || AM29K
  1586.       PERFORM_SHIFTL(v, co, r1, VALUE(16), ci);
  1587.       RECURSE(SHIFTL, s1, CNST(16), prune_hint & ~CY_JUST_SET);
  1588. #endif
  1589. #if RS6000 || M88000
  1590.       PERFORM_ROTATEL(v, co, r1, VALUE(16), ci);
  1591.       RECURSE(ROTATEL, s1, CNST(16), prune_hint & ~CY_JUST_SET);
  1592. #endif
  1593. #endif /* SHIFT16 */
  1594. #endif /* SHIFTS */
  1595. #if EXTRACTS
  1596.       {
  1597.     int cnt;
  1598.     for (cnt = 1; cnt < BITS_PER_WORD; cnt++)
  1599.       {
  1600. #if M88000
  1601.         PERFORM_EXTS1(v, co, r1, VALUE(cnt), ci);
  1602.         RECURSE(EXTS1, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1603.         PERFORM_EXTU1(v, co, r1, VALUE(cnt), ci);
  1604.         RECURSE(EXTU1, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1605.         PERFORM_EXTS2(v, co, r1, VALUE(cnt), ci);
  1606.         RECURSE(EXTS2, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1607.         PERFORM_EXTU2(v, co, r1, VALUE(cnt), ci);
  1608.         RECURSE(EXTU2, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1609. #endif
  1610.       }
  1611.       }
  1612. #endif
  1613. #if AM29K
  1614.       PERFORM_CPEQ(v, co, r1, VALUE(0), ci);
  1615.       RECURSE(CPEQ, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1616.       PERFORM_CPGE(v, co, r1, VALUE(0), ci);
  1617.       RECURSE(CPGE, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1618.       PERFORM_CPGEU(v, co, r1, VALUE(0), ci);
  1619.       RECURSE(CPGEU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1620.       PERFORM_CPGT(v, co, r1, VALUE(0), ci);
  1621.       RECURSE(CPGT, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1622.       PERFORM_CPGTU(v, co, r1, VALUE(0), ci);
  1623.       RECURSE(CPGTU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1624.       PERFORM_CPLE(v, co, r1, VALUE(0), ci);
  1625.       RECURSE(CPLE, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1626.       PERFORM_CPLEU(v, co, r1, VALUE(0), ci);
  1627.       RECURSE(CPLEU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1628.       PERFORM_CPLT(v, co, r1, VALUE(0), ci);
  1629.       RECURSE(CPLT, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1630.       PERFORM_CPLTU(v, co, r1, VALUE(0), ci);
  1631.       RECURSE(CPLTU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1632.       PERFORM_CPNEQ(v, co, r1, VALUE(0), ci);
  1633.       RECURSE(CPNEQ, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1634. #endif
  1635. #if RS6000 || AM29K
  1636.       PERFORM_CLZ(v, co, r1, ci);
  1637.       RECURSE(CLZ, s1, 0, prune_hint & ~CY_JUST_SET);
  1638. #endif
  1639. #if M88000
  1640.       PERFORM_FF1(v, co, r1, ci);
  1641.       RECURSE(FF1, s1, 0, prune_hint & ~CY_JUST_SET);
  1642. #endif
  1643. #if M88000
  1644.       PERFORM_CMPPAR (v, co, r1, VALUE(0), ci);
  1645.       RECURSE(CMPPAR, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1646.       PERFORM_CMPPAR (v, co, VALUE(0), r1, ci);
  1647.       RECURSE(CMPPAR, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1648. #endif
  1649.     }
  1650.  
  1651.   /* 0-ary instructions, just dependent on carry.  */
  1652.   if (ci >= 0 && flag_use_carry
  1653.       && (allowed_cost <= 1 ? ((prune_hint & CY_JUST_SET) != 0) : 1))
  1654.     {
  1655.       /* We don't do "0 - 1 - cy" or "0 + 1 + cy" here.  It would
  1656.      probably give few new sequences. */
  1657. #if SPARC || M88000
  1658.       /* d = cy, cy = 0. [Is it ever useful to set cy unconditionally?]
  1659.      sparc:        addxcc    %g0,0,d
  1660.      m88000:    addu.cio d,r0,r0 */
  1661.       PERFORM_ADD_CIO(v, co, VALUE(0), VALUE(0), ci);
  1662.       RECURSE(ADD_CIO, CNST(0), CNST(0), CY_JUST_SET | CY_0);
  1663. #endif
  1664. #if SPARC
  1665.       /* d = -cy, cy = cy
  1666.      sparc:        subxcc    %g0,0,d */
  1667.       PERFORM_SUB_CIO(v, co, VALUE(0), VALUE(0), ci);
  1668.       RECURSE(SUB_CIO, CNST(0), CNST(0), prune_hint & ~CY_JUST_SET);
  1669. #endif
  1670. #if SPARC
  1671.       /* d = 1 - cy, cy = 1. [Is it ever useful to set cy unconditionally?]
  1672.      sparc:        subxcc    %g0,-1,d */
  1673.       PERFORM_SUB_CIO(v, co, VALUE(0), VALUE(-1), ci);
  1674.       RECURSE(SUB_CIO, CNST(0), CNST(-1), CY_JUST_SET | CY_1);
  1675. #endif
  1676. #if SPARC
  1677.       /* d = -1 + cy, cy = cy
  1678.      sparc:        addxcc    %g0,-1,d */
  1679.       PERFORM_ADD_CIO(v, co, VALUE(0), VALUE(-1), ci);
  1680.       RECURSE(ADD_CIO, CNST(0), CNST(-1), prune_hint & ~CY_JUST_SET);
  1681. #endif
  1682. #if RS6000 || AM29K /* Use subu.ci on 88k instead with same result */
  1683.       /* d = -1 + cy, cy = cy
  1684.      m88000:    subu.cio d,r0,r0
  1685.      rs6000:    sfe    d,d,d
  1686.      am29k:        subc    d,d,d */
  1687.       PERFORM_ADC_CIO(v, co, VALUE(0), VALUE(0), ci);
  1688.       RECURSE(ADC_CIO, n_values, n_values, prune_hint & ~CY_JUST_SET);
  1689. #endif
  1690. #if M88000
  1691.       /* d = -1 + cy
  1692.      m88000:    subu.ci    d,r0,r0 */
  1693.       PERFORM_ADC_CI(v, co, VALUE(0), VALUE(0), ci);
  1694.       RECURSE(ADC_CI, n_values, n_values, prune_hint & ~CY_JUST_SET);
  1695. #endif
  1696.     }
  1697.  
  1698.   /* Move instructions.
  1699.      Don't do this if we are just permitted to do one more instruction.  */
  1700.   if (allowed_cost > 1)
  1701.     {
  1702. #if SPARC || RS6000 || M88000 || AM29K
  1703.       /* d = 0x80000000
  1704.      sparc:        sethi    %hi(0x80000000),d
  1705.      rs6000:    liu    d,0x8000
  1706.      m88000:    or.u    d,r0,0x8000
  1707.      am29k:        cpeq    d,gr1,gr1 */
  1708.       PERFORM_COPY(v, co, VALUE_MIN_SIGNED, ci);
  1709.       RECURSE(COPY, CNST_0x80000000, 0, prune_hint & ~CY_JUST_SET);
  1710.       /* d = -1
  1711.      sparc:        mov    -1,d
  1712.      rs6000:    lil    d,-1
  1713.      m88000:    subu    d,r0,1
  1714.      am29k:        constn    d,1 */
  1715.       PERFORM_COPY(v, co, VALUE(-1), ci);
  1716.       RECURSE(COPY, CNST(-1), 0, prune_hint & ~CY_JUST_SET);
  1717.       /* d = 1
  1718.      sparc:        mov    1,d
  1719.      rs6000:    lil    d,1
  1720.      m88000:    addu    d,r0,1
  1721.      am29k:        const    d,1 */
  1722.       PERFORM_COPY(v, co, VALUE(1), ci);
  1723.       RECURSE(COPY, CNST(1), 0, prune_hint & ~CY_JUST_SET);
  1724. #endif
  1725. #if RS6000 || AM29K    /* sparc and 88k should not need this. */
  1726.       /* d = 0
  1727.      sparc:        mov    0,d
  1728.      rs6000:    lil    d,0
  1729.      m88000:    or    d,r0,0
  1730.      am29k:        const    d,0 */
  1731.       PERFORM_COPY(v, co, VALUE(0), ci);
  1732.       RECURSE(COPY, CNST(0), 0, prune_hint & ~CY_JUST_SET);
  1733. #endif
  1734. #if M88000
  1735.       /* d = 0x7fffffff
  1736.      m88000:    set    d,r0,31<0> */
  1737.       PERFORM_COPY(v, co, VALUE_MAX_SIGNED, ci);
  1738.       RECURSE(COPY, CNST_0x7FFFFFFF, 0, prune_hint & ~CY_JUST_SET);
  1739. #endif
  1740.     }
  1741.  
  1742. #ifdef TIMING
  1743.   time[allowed_cost] += cputime() - time_start;
  1744. #endif
  1745. }
  1746. #endif
  1747.  
  1748. /* This function is commented above, before the previous function.  */
  1749.  
  1750. #if M68000 || I386 || PYR
  1751. void
  1752. synth(insn_t *sequence,
  1753.       int n_insns,
  1754.       word *values,
  1755.       int n_values,
  1756.       word goal_value,
  1757.       int allowed_cost,
  1758.       int ci,
  1759.       int prune_hint)
  1760. {
  1761.   int s1, s2;
  1762.   word v, r1, r2;
  1763.   int co;
  1764.   int last_dest;
  1765.  
  1766.   if (n_insns > 0)
  1767.     last_dest = sequence[n_insns - 1].d;
  1768.   else
  1769.     last_dest = -1;
  1770.  
  1771.   /* Binary operations with carry-in.  */
  1772.   if (ci >= 0 && (prune_hint & CY_0) == 0 && flag_use_carry)
  1773.     {
  1774.       for (s1 = n_values - 1; s1 >= 0; s1--)
  1775.     {
  1776.       r1 = values[s1];
  1777.       for (s2 = n_values - 1; s2 >= 0; s2--)
  1778.         {
  1779.           r2 = values[s2];
  1780.  
  1781.           if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
  1782.         {
  1783.           /* We are in a leaf node.  CY was not set (to 1 or to a
  1784.              data dependent value) by the previous insn.
  1785.  
  1786.              So one of the input operands has to be the result
  1787.              operand of the previous insn for that insn to be
  1788.              meaningful.  */
  1789.           if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
  1790.             continue;
  1791.         }
  1792.  
  1793. #if M68000 || I386 || PYR
  1794.           /* m68000:    addx
  1795.          i80386:    adc
  1796.          pyramid:    addwc */
  1797.           PERFORM_ADD_CIO(v, co, r1, r2, ci);
  1798.           CRECURSE_2OP(ADD_CIO, s1, s1, s2, 1, CY_JUST_SET);
  1799. #endif
  1800. #if M68000 || I386
  1801.           if (s1 != s2)
  1802.         {
  1803.           /* m68000:    subx
  1804.              i80386:    sbb */
  1805.           PERFORM_SUB_CIO(v, co, r1, r2, ci);
  1806.           CRECURSE_2OP(SUB_CIO, s1, s1, s2, 1, CY_JUST_SET);
  1807.         }
  1808. #endif
  1809. #if PYR
  1810.           if (s1 != s2)
  1811.         {
  1812.           /* pyramid:    subwb */
  1813.           PERFORM_ADC_CIO(v, co, r1, r2, ci);
  1814.           CRECURSE_2OP(ADC_CIO, s1, s1, s2, 1, CY_JUST_SET);
  1815.         }
  1816. #endif
  1817.         }
  1818.     }
  1819.     }
  1820.  
  1821.   /* Binary operations without carry-in.  */
  1822.   for (s1 = n_values - 1; s1 >= 0; s1--)
  1823.     {
  1824.       r1 = values[s1];
  1825.       for (s2 = n_values - 1; s2 >= 0; s2--)
  1826.     {
  1827.       r2 = values[s2];
  1828.  
  1829.       if (allowed_cost <= 1)
  1830.         {
  1831.           /* We are in a leaf node.
  1832.  
  1833.          So one of the input operands has to be the result operand
  1834.          of the previous insn for that insn to be meaningful.  */
  1835.           if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
  1836.         continue;
  1837.         }
  1838.  
  1839. #if M68000 || I386 || PYR
  1840.       /* m68000:    add
  1841.          i80386:    add
  1842.          pyramid:    addw */
  1843.       PERFORM_ADD_CO(v, co, r1, r2, ci);
  1844.       CRECURSE_2OP(ADD_CO, s1, s1, s2, 1, CY_JUST_SET);
  1845. #endif
  1846.       if (s1 != s2)
  1847.         {
  1848. #if M68000 || I386
  1849.           /* m68000:    sub
  1850.          i80386:    sub */
  1851.           PERFORM_SUB_CO(v, co, r1, r2, ci);
  1852.           CRECURSE_2OP(SUB_CO, s1, s1, s2, 1, CY_JUST_SET);
  1853. #endif
  1854. #if PYR
  1855.           /* pyramid:    subw */
  1856.           PERFORM_ADC_CO(v, co, r1, r2, ci);
  1857.           CRECURSE_2OP(ADC_CO, s1, s1, s2, 1, CY_JUST_SET);
  1858. #endif
  1859. #if M68000
  1860.           PERFORM_AND(v, co, r1, r2, ci);
  1861.           CRECURSE_2OP(AND, s1, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  1862.  
  1863.           PERFORM_IOR(v, co, r1, r2, ci);
  1864.           CRECURSE_2OP(IOR, s1, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  1865.  
  1866.           PERFORM_XOR(v, co, r1, r2, ci);
  1867.           CRECURSE_2OP(XOR, s1, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  1868. #endif
  1869. #if I386
  1870.           PERFORM_AND_RC(v, co, r1, r2, ci);
  1871.           CRECURSE_2OP(AND_RC, s1, s1, s2, 1, CY_JUST_SET | CY_0);
  1872.  
  1873.           PERFORM_IOR_RC(v, co, r1, r2, ci);
  1874.           CRECURSE_2OP(IOR_RC, s1, s1, s2, 1, CY_JUST_SET | CY_0);
  1875.  
  1876.           PERFORM_XOR_RC(v, co, r1, r2, ci);
  1877.           CRECURSE_2OP(XOR_RC, s1, s1, s2, 1, CY_JUST_SET | CY_0);
  1878. #endif
  1879. #if PYR
  1880.           PERFORM_AND_CC(v, co, r1, r2, ci);
  1881.           CRECURSE_2OP(AND_CC, s1, s1, s2, 1, 0);
  1882.  
  1883.           PERFORM_ANDC_CC(v, co, r1, r2, ci);
  1884.           CRECURSE_2OP(ANDC_CC, s1, s1, s2, 1, 0);
  1885.  
  1886.           PERFORM_IOR_CC(v, co, r1, r2, ci);
  1887.           CRECURSE_2OP(IOR_CC, s1, s1, s2, 1, 0);
  1888.  
  1889.           PERFORM_XOR_CC(v, co, r1, r2, ci);
  1890.           CRECURSE_2OP(XOR_CC, s1, s1, s2, 1, 0);
  1891. #endif
  1892. #if I386
  1893.           PERFORM_CMP(v, co, r1, r2, ci);
  1894.           /* kludge: lie that the result is written to
  1895.          register <n_values>. */
  1896.           CRECURSE_2OP(CMP, n_values, s1, s2, 1, CY_JUST_SET);
  1897. #endif
  1898.         }
  1899. #if M68000 || I386 || PYR
  1900.       /* Exchange registers.  An ugly kludge.  */
  1901.       if (s1 < s2)
  1902.         {
  1903.           values[s2] = r1;
  1904.           /* Assign r2 to v to make `recurse' and rely on `recurse'
  1905.          to handle the writing of it to the values array.  */
  1906.           v = r2;
  1907.           CRECURSE_2OP(EXCHANGE, s1, s1, s2, 1,
  1908.                prune_hint & ~CY_JUST_SET);
  1909.           values[s2] = r2;
  1910.         }
  1911. #endif
  1912.     }
  1913.     }
  1914.  
  1915.   /* Unary operations with carry-in.  */
  1916.   if (ci >= 0 && (prune_hint & CY_0) == 0 && flag_use_carry)
  1917.     {
  1918.       for (s1 = n_values - 1; s1 >= 0; s1--)
  1919.     {
  1920.       r1 = values[s1];
  1921.  
  1922.       if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
  1923.         {
  1924.           /* We are in a leaf node.  CY was not set (to 1 or to a
  1925.          data dependent value) by the previous insn.
  1926.  
  1927.          The input operand has to be the result operand of the
  1928.          previous insn for that insn to be meaningful.  */
  1929.           if (last_dest >= 0 && s1 != last_dest)
  1930.         continue;
  1931.         }
  1932.  
  1933. #if I386 || PYR
  1934.       /* d,cy = r1 + 1 + cy
  1935.          i80386:    adc    1,d
  1936.          pyramid:    addwc    $1,d */
  1937.       PERFORM_ADD_CIO(v, co, r1, VALUE(1), ci);
  1938.       CRECURSE_2OP(ADD_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
  1939. #endif
  1940. #if I386
  1941.       /* d,cy = r1 - 1 - cy
  1942.          i80386:    sbb    1,d */
  1943.       PERFORM_SUB_CIO(v, co, r1, VALUE(1), ci);
  1944.       CRECURSE_2OP(SUB_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
  1945. #endif
  1946. #if PYR
  1947.       /* d,cy = r1 + (-2) + cy
  1948.          pyramid:    subwb    $1,d */
  1949.       PERFORM_ADC_CIO(v, co, r1, VALUE(1), ci);
  1950.       CRECURSE_2OP(ADC_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
  1951. #endif
  1952. #if I386 || PYR
  1953.       /* d,cy = r1 + (-1) + cy
  1954.          i80386:    adc    -1,d
  1955.          pyramid:    addwc    $-1,d */
  1956.       PERFORM_ADD_CIO(v, co, r1, VALUE(-1), ci);
  1957.       CRECURSE_2OP(ADD_CIO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  1958. #endif
  1959. #if I386
  1960.       /* d,cy = r1 - -1 - cy
  1961.          i80386:    sbb    -1,d */
  1962.       PERFORM_SUB_CIO(v, co, r1, VALUE(-1), ci);
  1963.       CRECURSE_2OP(SUB_CIO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  1964. #endif
  1965. #if PYR
  1966.       /* d,cy = r1 + cy          [or if you prefer, r1 + 0 + cy]
  1967.          pyramid:    subwb    $-1,d */
  1968.       PERFORM_ADC_CIO(v, co, r1, VALUE(-1), ci);
  1969.       CRECURSE_2OP(ADC_CIO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  1970. #endif
  1971. #if I386 || PYR
  1972.       /* d,cy = r1 + cy
  1973.          i80386:    adc    0,d
  1974.          pyramid:    addwc    $0,d */
  1975.       PERFORM_ADD_CIO(v, co, r1, VALUE(0), ci);
  1976.       CRECURSE_2OP(ADD_CIO, s1, s1, CNST(0), 1, CY_JUST_SET);
  1977. #endif
  1978. #if I386
  1979.       /* d,cy = r1 - cy
  1980.          i80386:    sbb    0,d */
  1981.       PERFORM_SUB_CIO(v, co, r1, VALUE(0), ci);
  1982.       CRECURSE_2OP(SUB_CIO, s1, s1, CNST(0), 1, CY_JUST_SET);
  1983. #endif
  1984. #if PYR
  1985.       /* d,cy = r1 + (-1) + cy
  1986.          pyramid:    subwb    $0,d */
  1987.       PERFORM_ADC_CIO(v, co, r1, VALUE(0), ci);
  1988.       CRECURSE_2OP(ADC_CIO, s1, s1, CNST(0), 1, CY_JUST_SET);
  1989. #endif
  1990. #if M68000
  1991.       /* d,cy = 0 - r1 - cy
  1992.          m68000:     negx    d */
  1993.       PERFORM_SUB_CIO(v, co, VALUE(0), r1, ci);
  1994.       CRECURSE_2OP(SUB_CIO, s1, CNST(0), s1, 1, CY_JUST_SET);
  1995. #endif
  1996. #if M68000
  1997.       /* d,cy = circular rotate left thru carry
  1998.          m68000:    roxll    #1,d */
  1999.       PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(1), ci);
  2000.       CRECURSE_2OP(ROTATEXL_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2001. #endif
  2002. #if I386
  2003.       PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2004.       CRECURSE_2OP(ROTATEXL_CIO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2005.  
  2006.       PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(1), ci);
  2007.       CRECURSE_2OP(ROTATEXL_CIO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2008. #endif
  2009.     }
  2010.     }
  2011.  
  2012.   /* Unary operations without carry-in.  */
  2013.   for (s1 = n_values - 1; s1 >= 0; s1--)
  2014.     {
  2015.       r1 = values[s1];
  2016.  
  2017.       if (allowed_cost <= 1)
  2018.     {
  2019.       /* We are in a leaf node.
  2020.  
  2021.          The input operand has to be the result operand of the
  2022.          previous insns for that insn to be meaningful.  */
  2023.       if (last_dest >= 0 && s1 != last_dest)
  2024.         continue;
  2025.     }
  2026.       else
  2027.     {
  2028.       /* Certain instructions should not terminate a sequence.  So we
  2029.          only generate them in non-leaf nodes.  */
  2030. #if M68000 || I386 || PYR
  2031.       /* d = r1
  2032.          m68000:    move    s1,d
  2033.          i80386:    move    s1,d
  2034.          pyramid:    movw    s1,d */
  2035.       PERFORM_COPY(v, co, r1, ci);
  2036.       CRECURSE_NEW(COPY, n_values, s1, CNST(0), 1,
  2037.                prune_hint & ~CY_JUST_SET);
  2038. #endif
  2039. #if I386
  2040.       /* cmp kludge: lie that the result is written to register
  2041.          <n_values>. */
  2042.  
  2043.       /* i80386:    cmp    -1,s1 */
  2044.       PERFORM_CMP(v, co, r1, VALUE(-1), ci);
  2045.       CRECURSE_2OP(CMP, n_values, s1, CNST(-1), 1, CY_JUST_SET);
  2046.  
  2047.       /* i80386:    cmp    1,s1 */
  2048.       PERFORM_CMP(v, co, r1, VALUE(1), ci);
  2049.       CRECURSE_2OP(CMP, n_values, s1, CNST(1), 1, CY_JUST_SET);
  2050.  
  2051.       /* i80386:    cmp    0x7fffffff,s1 */
  2052.       PERFORM_CMP(v, co, r1, VALUE_MAX_SIGNED, ci);
  2053.       CRECURSE_2OP(CMP, n_values, s1, CNST_0x7FFFFFFF, 2, CY_JUST_SET);
  2054.  
  2055.       /* i80386:    cmp    0x80000000,s1 */
  2056.       PERFORM_CMP(v, co, r1, VALUE_MIN_SIGNED, ci);
  2057.       CRECURSE_2OP(CMP, n_values, s1, CNST_0x80000000, 2, CY_JUST_SET);
  2058. #endif
  2059.     }
  2060.  
  2061. #if M68000 || PYR
  2062.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(1), ci);
  2063.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2064.  
  2065.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(1), ci);
  2066.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2067.  
  2068.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(1), ci);
  2069.       CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2070.  
  2071.       /* Pyramids's rotlw and rotrw clobber cy */
  2072. #endif
  2073. #if M68000
  2074.       PERFORM_ROTATEL_CO(v, co, r1, VALUE(1), ci);
  2075.       CRECURSE_2OP(ROTATEL_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2076. #endif
  2077. #if PYR
  2078.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2079.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 1, CY_JUST_SET);
  2080.  
  2081.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2082.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 1, CY_JUST_SET);
  2083.  
  2084.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2085.       CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(BITS_PER_WORD-1), 1, CY_JUST_SET);
  2086.  
  2087.       /* Pyramids's rotlw and rotrw clobber cy */
  2088. #endif
  2089. #if I386
  2090.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2091.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2092.  
  2093.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2094.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2095.  
  2096.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2097.       CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2098.  
  2099.       PERFORM_ROTATEL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2100.       CRECURSE_2OP(ROTATEL_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2101.  
  2102.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(1), ci);
  2103.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2104.  
  2105.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(1), ci);
  2106.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2107.  
  2108.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(1), ci);
  2109.       CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2110.  
  2111.       PERFORM_ROTATEL_CO(v, co, r1, VALUE(1), ci);
  2112.       CRECURSE_2OP(ROTATEL_CO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2113. #endif
  2114. #if M68000
  2115.       PERFORM_AND(v, co, r1, VALUE_MIN_SIGNED, ci);
  2116.       CRECURSE_2OP(AND, s1, s1, CNST_0x80000000, 2,
  2117.            prune_hint & ~CY_JUST_SET);
  2118.  
  2119.       PERFORM_IOR(v, co, r1, VALUE_MIN_SIGNED, ci);
  2120.       CRECURSE_2OP(IOR, s1, s1, CNST_0x80000000, 2,
  2121.            prune_hint & ~CY_JUST_SET);
  2122.  
  2123.       PERFORM_XOR(v, co, r1, VALUE_MIN_SIGNED, ci);
  2124.       CRECURSE_2OP(XOR, s1, s1, CNST_0x80000000, 2,
  2125.            prune_hint & ~CY_JUST_SET);
  2126. #endif
  2127. #if I386
  2128.       PERFORM_AND_RC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2129.       CRECURSE_2OP(AND_RC, s1, s1, CNST_0x80000000, 2, CY_JUST_SET | CY_0);
  2130.  
  2131.       PERFORM_IOR_RC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2132.       CRECURSE_2OP(IOR_RC, s1, s1, CNST_0x80000000, 2, CY_JUST_SET | CY_0);
  2133.  
  2134.       PERFORM_XOR_RC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2135.       CRECURSE_2OP(XOR_RC, s1, s1, CNST_0x80000000, 2, CY_JUST_SET | CY_0);
  2136. #endif
  2137. #if PYR
  2138.       PERFORM_AND_CC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2139.       CRECURSE_2OP(AND_CC, s1, s1, CNST_0x80000000, 2, 0);
  2140.  
  2141.       PERFORM_IOR_CC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2142.       CRECURSE_2OP(IOR_CC, s1, s1, CNST_0x80000000, 2, 0);
  2143.  
  2144.       PERFORM_XOR_CC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2145.       CRECURSE_2OP(XOR_CC, s1, s1, CNST_0x80000000, 2, 0);
  2146. #endif
  2147. #if M68000
  2148.       /* d = r1 ^ 1
  2149.      m68000:    eorw    #1,d */
  2150.       PERFORM_XOR(v, co, r1, VALUE(1), ci);
  2151.       CRECURSE_2OP(XOR, s1, s1, CNST(1), 1, prune_hint & ~CY_JUST_SET);
  2152. #endif
  2153. #if I386
  2154.       /* d = r1 ^ 1
  2155.      i80386:    xorb    $1,d */
  2156.       PERFORM_XOR_RC(v, co, r1, VALUE(1), ci);
  2157.       CRECURSE_2OP(XOR_RC, s1, s1, CNST(1), 1, CY_JUST_SET | CY_0);
  2158. #endif
  2159. #if PYR
  2160.       /* d = r1 ^ 1
  2161.      pyramid:    xorw    $1,d */
  2162.       PERFORM_XOR_CC(v, co, r1, VALUE(1), ci);
  2163.       CRECURSE_2OP(XOR_CC, s1, s1, CNST(1), 1, 0);
  2164. #endif
  2165. #if M68000 || I386
  2166.       /* d = ~r1
  2167.      m68000:    not    d
  2168.      i80386:    not    d */
  2169.       PERFORM_SUB(v, co, VALUE(-1), r1, ci);
  2170.       CRECURSE_2OP(SUB, s1, CNST(-1), s1, 1, prune_hint & ~CY_JUST_SET);
  2171. #endif
  2172. #if PYR
  2173.       /* d = ~r1
  2174.      pyramid:    mcomw    s1,d */
  2175.       /* We need a new insn: SUB_CC, for Subtract and Clobber Carry  */
  2176. #endif
  2177. #if I386
  2178.       /* d = r1 + 1
  2179.      i80386:    inc    d */
  2180.       PERFORM_ADD(v, co, r1, VALUE(1), ci);
  2181.       CRECURSE_2OP(ADD, s1, s1, CNST(1), 2, prune_hint & ~CY_JUST_SET);
  2182. #endif
  2183. #if PYR
  2184.       /* d = r1 + 1
  2185.      pyramid:    mova    1(s1),d */
  2186.       PERFORM_ADD(v, co, r1, VALUE(1), ci);
  2187.       RECURSE(ADD, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  2188. #endif
  2189. #if I386
  2190.       /* d = r1 - 1
  2191.      i80386:    dec    d */
  2192.       PERFORM_SUB(v, co, r1, VALUE(1), ci);
  2193.       CRECURSE_2OP(SUB, s1, s1, CNST(1), 1, prune_hint & ~CY_JUST_SET);
  2194. #endif
  2195. #if PYR
  2196.       /* d = r1 - 1
  2197.      pyramid:    mova    -1(s1),d */
  2198.       PERFORM_ADD(v, co, r1, VALUE(-1), ci);
  2199.       RECURSE(ADD, s1, CNST(-1), prune_hint & ~CY_JUST_SET);
  2200. #endif
  2201. #if M68000 || I386 || PYR
  2202.       /* d,cy = r1 + 1
  2203.      m68000:    addq    1,d
  2204.      i80386:    add    1,d [short immediate form]
  2205.      pyramid:    addw    $1,d */
  2206.       PERFORM_ADD_CO(v, co, r1, VALUE(1), ci);
  2207.       CRECURSE_2OP(ADD_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2208. #endif
  2209. #if M68000 || I386
  2210.       /* d,cy = r1 - 1
  2211.      m68000:    subq    1,d
  2212.      i80386:    sub    1,d [short immediate form] */
  2213.       PERFORM_SUB_CO(v, co, r1, VALUE(1), ci);
  2214.       CRECURSE_2OP(SUB_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2215. #endif
  2216. #if PYR && 0            /* same effect as addw $-1,d */
  2217.       /* d,cy = r1 + (-1)
  2218.      pyramid:    subw    1,d */
  2219.       PERFORM_ADC_CO(v, co, r1, VALUE(1), ci);
  2220.       CRECURSE_2OP(ADC_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2221. #endif
  2222. #if M68000
  2223.       /* d,cy = r1 + (-1)
  2224.      m68000:    add    -1,d */
  2225.       PERFORM_ADD_CO(v, co, r1, VALUE(-1), ci);
  2226.       CRECURSE_2OP(ADD_CO, s1, s1, CNST(-1), 2, CY_JUST_SET);
  2227. #endif
  2228. #if I386 || PYR
  2229.       /* d,cy = r1 + (-1)
  2230.      i80386:    add    -1,d
  2231.      pyramid:    addw    $-1,d */
  2232.       PERFORM_ADD_CO(v, co, r1, VALUE(-1), ci);
  2233.       CRECURSE_2OP(ADD_CO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  2234. #endif
  2235. #if M68000
  2236.       /* d,cy = r1 - (-1)
  2237.      m68000:    sub    -1,d */
  2238.       PERFORM_SUB_CO(v, co, r1, VALUE(-1), ci);
  2239.       CRECURSE_2OP(SUB_CO, s1, s1, CNST(-1), 2, CY_JUST_SET);
  2240. #endif
  2241. #if I386
  2242.       /* d,cy = r1 - (-1)
  2243.      i80386:    sub    -1,d */
  2244.       PERFORM_SUB_CO(v, co, r1, VALUE(-1), ci);
  2245.       CRECURSE_2OP(SUB_CO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  2246. #endif
  2247. #if M68000 || I386
  2248.       /* d,cy = -r1
  2249.      m68000:    neg    d
  2250.      i80386:    neg    d */
  2251.       PERFORM_SUB_CO(v, co, VALUE(0), r1, ci);
  2252.       CRECURSE_2OP(SUB_CO, s1, CNST(0), s1, 1, CY_JUST_SET);
  2253. #endif
  2254. #if PYR
  2255.       /* d,cy = 0 + (-r1)
  2256.      pyramid:    rsubw    $0,d */
  2257.       PERFORM_ADC_CO(v, co, VALUE(0), r1, ci);
  2258.       CRECURSE_2OP(ADC_CO, s1, CNST(0), s1, 1, CY_JUST_SET);
  2259. #endif
  2260.     }
  2261.  
  2262. #if M68000
  2263.   /* kludge for immediate shift on 68k */
  2264.   if (last_dest >= 0 && last_dest == n_values - 1
  2265.       && values[last_dest] == VALUE(BITS_PER_WORD-1)
  2266.       && sequence[n_insns - 1].opcode == COPY)
  2267.     {
  2268.       for (s1 = n_values - 2; s1 >= 0; s1--)
  2269.     {
  2270.       r1 = values[s1];
  2271.  
  2272.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2273.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, last_dest, 1, CY_JUST_SET);
  2274.  
  2275.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2276.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, last_dest, 1, CY_JUST_SET);
  2277.  
  2278.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2279.       CRECURSE_2OP(SHIFTL_CO, s1, s1, last_dest, 1, CY_JUST_SET);
  2280.  
  2281.       PERFORM_ROTATEL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2282.       CRECURSE_2OP(ROTATEL_CO, s1, s1, last_dest, 1, CY_JUST_SET);
  2283.  
  2284.       if (ci >= 0)
  2285.         {
  2286.           PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2287.           CRECURSE_2OP(ROTATEXL_CIO, s1, s1, last_dest, 1, CY_JUST_SET);
  2288.         }
  2289.     }
  2290.     }
  2291. #endif
  2292.  
  2293.   if (ci >= 0 && (prune_hint & CY_0) == 0 && flag_use_carry
  2294.       && (allowed_cost <= 1 ? ((prune_hint & CY_JUST_SET) != 0) : 1))
  2295.     {
  2296. #if M68000 || I386
  2297.       /* d = -cy, cy = cy
  2298.      m68000:    subx    d,d
  2299.      i80386:    sbb    d,d */
  2300.       PERFORM_SUB_CIO(v, co, VALUE(0), VALUE(0), ci);
  2301.       CRECURSE_NEW(SUB_CIO, n_values, n_values, n_values, 1,
  2302.            prune_hint & ~CY_JUST_SET); /* cy not really affected */
  2303. #endif
  2304. #if PYR
  2305.       /* d = -cy, cy = cy
  2306.      pyramid:    subwb    d,d */
  2307.       PERFORM_ADC_CIO(v, co, VALUE(0), VALUE(0), ci);
  2308.       CRECURSE_NEW(ADC_CIO, n_values, n_values, n_values, 1,
  2309.            prune_hint & ~CY_JUST_SET); /* cy not really affected */
  2310. #endif
  2311. #if I386 /* slow on m68000 */
  2312.       /* i80386:    cmc */
  2313.       co = ci ^ 1;
  2314.       CRECURSE_2OP(COMCY, n_values, n_values, n_values, 1, CY_JUST_SET);
  2315. #endif
  2316.     }
  2317.  
  2318.   /* Move instructions.
  2319.      Don't do this if we are just permitted to do one more instruction.  */
  2320.   if (allowed_cost > 1)
  2321.     {
  2322. #if M68000 || PYR
  2323.       /* d = 0
  2324.      m68000:    moveq    0,d
  2325.      pyramid:    movw    0,d */
  2326.       PERFORM_COPY(v, co, VALUE(0), ci);
  2327.       CRECURSE_NEW(COPY, n_values, CNST(0), CNST(0), 1,
  2328.            prune_hint & ~CY_JUST_SET);
  2329. #endif
  2330. #if M68000 || I386
  2331.       /* d = 0, cy = 0
  2332.      m68000:    sub    d,d
  2333.      i80386:    sub    d,d */
  2334.       PERFORM_SUB_CO(v, co, r1, r1, ci);
  2335.       CRECURSE_NEW(SUB_CO, s1, s1, s1, 2, CY_JUST_SET | CY_0);
  2336. #endif
  2337. #if PYR
  2338.       /* d = 0, cy = 0
  2339.      pyramid:    subw    d,d */
  2340.       PERFORM_ADC_CO(v, co, r1, r1, ci);
  2341.       CRECURSE_NEW(ADC_CO, s1, s1, s1, 2, CY_JUST_SET | CY_0);
  2342. #endif
  2343. #if M68000
  2344.       /* d = 31
  2345.      m68000:    moveq    31,d */
  2346.       PERFORM_COPY(v, co, VALUE(BITS_PER_WORD-1), ci);
  2347.       CRECURSE_NEW(COPY, n_values, CNST(BITS_PER_WORD-1), CNST(0), 1,
  2348.            prune_hint & ~CY_JUST_SET);
  2349. #endif
  2350. #if M68000 || PYR
  2351.       /* d = 1
  2352.      m68000:    moveq    1,d
  2353.      pyramid:    movw    $1,d */
  2354.       PERFORM_COPY(v, co, VALUE(1), ci);
  2355.       CRECURSE_NEW(COPY, n_values, CNST(1), CNST(0), 1,
  2356.            prune_hint & ~CY_JUST_SET);
  2357.       /* d = -1
  2358.      m68000:    moveq    -1,d
  2359.      pyramid:    movw    $-1,d  */
  2360.       PERFORM_COPY(v, co, VALUE(-1), ci);
  2361.       CRECURSE_NEW(COPY, n_values, CNST(-1), CNST(0), 1,
  2362.            prune_hint & ~CY_JUST_SET);
  2363. #endif
  2364. #if M68000 || I386 || PYR    /* these cost 2 cost units */
  2365.       /* d = 0x80000000 */
  2366.       PERFORM_COPY(v, co, VALUE_MIN_SIGNED, ci);
  2367.       CRECURSE_NEW(COPY, n_values, CNST_0x80000000, CNST(0), 2,
  2368.            prune_hint & ~CY_JUST_SET);
  2369.  
  2370.       /* d = 0x7fffffff */
  2371.       PERFORM_COPY(v, co, VALUE_MAX_SIGNED, ci);
  2372.       CRECURSE_NEW(COPY, n_values, CNST_0x7FFFFFFF, CNST(0), 2,
  2373.            prune_hint & ~CY_JUST_SET);
  2374. #endif
  2375.     }
  2376. }
  2377. #endif
  2378.  
  2379. /* Call `synth' allowing deeper and deeper searches for each call.
  2380.    This way we achieve iterative deepening search.
  2381.  
  2382.    MAXMAX_COST is the maximum cost for any sequence we will accept.  */
  2383. void
  2384. main_synth(int maxmax_cost, int allowed_extra_cost)
  2385. {
  2386.   int max_cost;
  2387.   word values[0x100];
  2388.   insn_t sequence[0x100];
  2389.   int i, ii;
  2390.  
  2391.   init_immediates(tvalues);
  2392.   init_immediates(values);
  2393.   init_test_sets();
  2394.  
  2395.   /* Speed hack: Try to find random values that makes the goal function
  2396.      take a value != 0.  Many false sequences give 0 for all input,
  2397.      and this hack achieve quick reject of these sequences.  */
  2398.   for (i = 0; i < 50; i++)
  2399.     {
  2400.       for (ii = 0; ii < goal_function_arity; ii++)
  2401.     values[ii] = random_word();
  2402.       if ((*eval_goal_function)(values) != 0)
  2403.     break;
  2404.     }
  2405.  
  2406.   ii = 0;
  2407. #if KNOW_START
  2408.   switch (goal_function)
  2409.     {
  2410.     case FFS:
  2411. #if M88000
  2412.       /* Best ffs starting place.  */
  2413.       sequence[ii++] = (insn_t) { ADC_CO, CNST(0), 0, 1 };
  2414.       sequence[ii++] = (insn_t) { AND, 0, 1, 2 };
  2415. #endif
  2416.       break;
  2417.  
  2418.     case ZDEPI_FOR_MOVSI:
  2419. #if SPARC
  2420.       sequence[ii++] = (insn_t) { SUB, CNST(0), 0, 1 };
  2421.       sequence[ii++] = (insn_t) { AND, 0, 1, 2 };
  2422. #endif
  2423.       break;
  2424.     default: break;
  2425.     }
  2426. #endif
  2427.  
  2428.   fprintf(stderr, "Superoptimizing at cost");
  2429.   success = 0;
  2430.   for (max_cost = 1; max_cost <= maxmax_cost; max_cost++)
  2431.     {
  2432. #if TIMING
  2433.       for (i = 0; i <= max_cost; i++)
  2434.     time[i] = 0;
  2435. #endif
  2436.  
  2437.       if (success)
  2438.     fprintf (stderr, "[cost %d]\n", max_cost + ii);
  2439.       else
  2440.     fprintf(stderr, " %d", max_cost + ii);
  2441.       fflush(stderr);
  2442.  
  2443.       i = run_program (sequence, ii, values);
  2444.  
  2445.       /* Don't pass CY_JUST_SET ever, sice we don't know which of the
  2446.      predefined insn above set cy.  */
  2447.       synth(sequence, ii, values, goal_function_arity+ii,
  2448.         (*eval_goal_function)(values),
  2449.         max_cost, i, NO_PRUNE);
  2450.  
  2451. #ifdef STATISTICS
  2452.       if (isatty(fileno(stdout)) == isatty(fileno(stderr)))
  2453.     printf("\n");
  2454.       printf("heuristic accept count:%u\n", heuristic_accept_count);
  2455.       printf("heuristic reject count:%u\n", heuristic_reject_count);
  2456. #endif
  2457. #if TIMING
  2458.       for (i = 1; i <= max_cost; i++)
  2459.     printf ("time %d: %d\n", i, time[i] - time[i - 1]);
  2460. #endif
  2461.  
  2462.       if (success)
  2463.     {
  2464.       allowed_extra_cost--;
  2465.       if (allowed_extra_cost < 0)
  2466.         {
  2467.           static char *s[] = {"", "s"};
  2468.           fprintf(stderr, " [%d sequence%s found]\n", success,
  2469.               s[success != 1]);
  2470.           return;
  2471.         }
  2472.     }
  2473.     }
  2474.   fprintf(stderr, " failure.\n");
  2475. }
  2476.  
  2477. /* Create a function for each DEF_GOAL.  When optimized, these are very
  2478.    efficient.  */
  2479. #undef    DEF_GOAL
  2480. #ifdef __STDC__
  2481. #define DEF_GOAL(SYM,ARITY,NAME,CODE)         \
  2482. word SYM ## _func (const word *v)        \
  2483. GOAL_FUNCTION (ARITY, CODE)
  2484. #else
  2485. #define DEF_GOAL(SYM,ARITY,NAME,CODE)         \
  2486. word SYM/**/_func (v) word *v;            \
  2487. GOAL_FUNCTION (ARITY, CODE)
  2488. #endif
  2489. #define GOAL_FUNCTION(ARITY,CODE)        \
  2490. {                        \
  2491.   word r, v0, v1, v2, v3;            \
  2492.   switch (ARITY)                \
  2493.     {                        \
  2494.     default:                    \
  2495.       abort ();                    \
  2496.     case 4: v3 = v[3];                \
  2497.     case 3: v2 = v[2];                \
  2498.     case 2: v1 = v[1];                \
  2499.     case 1: v0 = v[0];                \
  2500.     }                        \
  2501.   CODE;                        \
  2502.   return r;                    \
  2503. }
  2504. #undef    DEF_SYNONYM
  2505. #define DEF_SYNONYM(SYM,NAME)
  2506. #include "goal.def"
  2507.  
  2508. struct
  2509. {
  2510.   char *fname;
  2511.   enum goal_func fcode;
  2512.   int arity;
  2513.   char *c_code;
  2514.   word (*function)(const word*);
  2515. } goal_table[] =
  2516. {
  2517. /* Start off with entries so that goal_names[i].fcode == i.  */
  2518. #undef    DEF_GOAL
  2519. #ifdef __STDC__
  2520. #define DEF_GOAL(SYM,ARITY,NAME,CODE) {NAME, SYM, ARITY, #CODE, SYM ## _func},
  2521. #else
  2522. #define DEF_GOAL(SYM,ARITY,NAME,CODE) {NAME, SYM, ARITY, "CODE", SYM/**/_func},
  2523. #endif
  2524. #undef    DEF_SYNONYM
  2525. #define DEF_SYNONYM(SYM,NAME)
  2526. #include "goal.def"
  2527.  
  2528. /* Now add the synonyms.  */
  2529. #undef    DEF_GOAL
  2530. #define DEF_GOAL(SYM,ARITY,NAME,CODE)
  2531. #undef    DEF_SYNONYM
  2532. #define DEF_SYNONYM(SYM,NAME) {NAME, SYM, 0, 0},
  2533. #include "goal.def"
  2534. };
  2535.  
  2536. #define GET_GOAL_NAME(X) (goal_table[X].fname)
  2537. #define GET_GOAL_ARITY(X) (goal_table[X].arity)
  2538. #define GET_GOAL_C_CODE(X) (goal_table[X].c_code)
  2539. #define GET_GOAL_FUNCTION(X) (goal_table[X].function)
  2540.  
  2541. int
  2542. main(int argc, char **argv)
  2543. {
  2544.   int maxmax_cost = 5;
  2545.   int allowed_extra_cost = 0;
  2546.   int flag_all = 0;
  2547.  
  2548.   goal_function = LAST_AND_UNUSED_GOAL_CODE;
  2549.  
  2550.   argv++;
  2551.   argc--;
  2552.  
  2553.   while (argc > 0)
  2554.     {
  2555.       char *arg = argv[0];
  2556.       int arglen = strlen(arg);
  2557.  
  2558.       if (arglen < 2)
  2559.     arglen = 2;
  2560.  
  2561.       if (!strncmp(arg, "-version", arglen))
  2562.     {
  2563.       printf ("GSO version %s\n", version_string);
  2564.       if (argc == 1)
  2565.         exit (0);
  2566.     }
  2567.       else if (!strncmp(arg, "-assembler", arglen))
  2568.     flag_output_assembler = 1;
  2569.       else if (!strncmp(arg, "-no-carry-insns", arglen))
  2570.     flag_use_carry = 0;
  2571.       else if (!strncmp(arg, "-all", arglen))
  2572.     flag_all = 1;
  2573.       else if (!strncmp(arg, "-max-cost", arglen))
  2574.     {
  2575.       argv++;
  2576.       argc--;
  2577.       if (argc == 0)
  2578.         {
  2579.           fprintf(stderr, "superoptimizer: argument to `-max-cost' expected\n");
  2580.           exit(-1);
  2581.         }
  2582.       maxmax_cost = atoi(argv[0]);
  2583.     }
  2584.       else if (!strncmp(arg, "-extra-cost", arglen))
  2585.     {
  2586.       argv++;
  2587.       argc--;
  2588.       if (argc == 0)
  2589.         {
  2590.           fprintf(stderr, "superoptimizer: argument `-extra-cost' expected\n");
  2591.           exit(-1);
  2592.         }
  2593.       allowed_extra_cost = atoi(argv[0]);
  2594.     }
  2595.       else if (!strncmp(arg, "-f", 2))
  2596.     {
  2597.       int i;
  2598.       for (i = 0; i < sizeof(goal_table) / sizeof(goal_table[0]); i++)
  2599.         {
  2600.           if (!strcmp(arg + 2, goal_table[i].fname))
  2601.         {
  2602.           goal_function = goal_table[i].fcode;
  2603.           goal_function_arity = GET_GOAL_ARITY(goal_function);
  2604.           eval_goal_function = GET_GOAL_FUNCTION(goal_function);
  2605.           break;
  2606.         }
  2607.         }
  2608.       if (goal_function == LAST_AND_UNUSED_GOAL_CODE)
  2609.         {
  2610.           fprintf(stderr,
  2611.               "superoptimizer: unknown goal function\n");
  2612.           exit(-1);
  2613.         }
  2614.     }
  2615.       else
  2616.     {
  2617.       fprintf(stderr, "superoptimizer: syntax error at command line\n");
  2618.       exit(-1);
  2619.     }
  2620.  
  2621.       argv++;
  2622.       argc--;
  2623.     }
  2624.  
  2625.   if (flag_all)
  2626.     {
  2627.       for (goal_function = 0; goal_function < LAST_AND_UNUSED_GOAL_CODE;
  2628.        goal_function++)
  2629.     {
  2630.       fprintf(stderr, "Searching for goal %s\n",
  2631.           GET_GOAL_NAME (goal_function));
  2632.  
  2633.       goal_function_arity = GET_GOAL_ARITY(goal_function);
  2634.       eval_goal_function = GET_GOAL_FUNCTION(goal_function);
  2635.       main_synth(maxmax_cost, allowed_extra_cost);
  2636.       if (success)
  2637.         fprintf(stderr, "%s\n", GET_GOAL_C_CODE(goal_function));
  2638.     }
  2639.       return 0;
  2640.     }
  2641.       
  2642.   if (goal_function == LAST_AND_UNUSED_GOAL_CODE)
  2643.     {
  2644.       fprintf(stderr, "superoptimizer: missing goal function definition\n");
  2645.       exit(-1);
  2646.     }
  2647.  
  2648.   fprintf(stderr, "Searching for %s\n", GET_GOAL_C_CODE(goal_function));
  2649.   main_synth(maxmax_cost, allowed_extra_cost);
  2650.   return !success;
  2651. }
  2652.  
  2653. /* Aux stuff that should go into a separate file.  */
  2654.  
  2655. const char clz_tab[] =
  2656. {
  2657.   32,31,30,30,29,29,29,29,28,28,28,28,28,28,28,28,
  2658.   27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,
  2659.   26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,
  2660.   26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,
  2661.   25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  2662.   25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  2663.   25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  2664.   25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  2665.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2666.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2667.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2668.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2669.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2670.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2671.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2672.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2673. };
  2674.  
  2675. const char ctz_tab[] =
  2676. {
  2677.   8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2678.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2679.   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2680.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2681.   6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2682.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2683.   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2684.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2685.   7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2686.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2687.   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2688.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2689.   6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2690.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2691.   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2692.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2693. };
  2694.  
  2695. const char ff1_tab[] =
  2696. {
  2697.   32,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,
  2698.   4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
  2699.   5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  2700.   5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  2701.   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  2702.   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  2703.   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  2704.   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  2705.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2706.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2707.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2708.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2709.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2710.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2711.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2712.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2713. };
  2714.